Once upon a time, long, long ago there lived a King and a Queen who ruled over a distant kingdom called Berland.
Their kingdom contained
n cities connected by
n-1 bi-directional roads. The roads were constructed in such a way that Berland citizens were able to reach any city from any other city by walking along these roads.
One day the King and the Queen decided that they want to break up the relationship. Yes, it's not common when it comes to a royal marriage, but it's something they decided to do and we have to respect their decision. Of course, now they want to divide the kingdom and start living separately from each other. Each of them wants to take a part of the existing kingdom. Moreover, they want their own parts to be very special, so their requirements are quite complicated.
So, the King wants to pick a nonempty subset of cities from the existing kingdom. He will be satisfied only if all following conditions are met:
- his subset of cities is connected (i.e. for every pair of his cities A and B, there is always a path from A to B that passes only through the King's cities),
- he does not share any cities with the Queen,
- none of his cities are directly connected by a road to any of the Queen's cities,
- if you consider distances between all pairs of his cities, the length of the longest path must be equal to D1,
- if you consider all pairs of his cities which are located at distance D1 from each other and then calculate the number of different cities within all these pairs, this number must not exceed C1 (formally, if his subset contains the only city then the number of such pairs equals 0).
The Queen wants to pick a nonempty subset of cities as well. Her requirements are essentially the same as the King's ones, with the exception of the numbers she has in mind —
D2 and
C2 respectively. Obviously, she is not allowed to take cities which have been already taken by the King, her subset of cities should be connected and none of her cities should be adjacent to the King's cities.
Now, what about the remaining cities, the ones that will not belong to either the King or the Queen after the kingdom is divided? The answer is simple — they have to be destroyed along with all roads coming into them, and all people should be evacuated from these cities. Destroying the
i-th city will cost
pi burles.
Can you help the King and the Queen with the separation? You task is to figure out whether it's possible to perform separation of the kingdom according to the rules described above. If the separation is possible, you have to find a way with the minimum possible cost of cities that will be destroyed.
Input
The first line of the input contains a positive integer
n (3 ≤
n ≤ 200) — the number of cities in the kingdom. The second line contains integers
D1,
C1,
D2,
C2 (0 ≤
D1,
D2 ≤
n-1, 1 ≤
C1,
C2 ≤
n). The third line contains
n integer costs
pi (1 ≤
pi ≤ 1000). Each of the next
n-1 lines contains two integer numbers
aj and
bj (1 ≤
aj,
bj ≤
n), meaning that the
j-th road connects cities
aj and
bj.
Output
If there is no solution, write "-1
" (without the quotes) in a single output line.
Otherwise, output the total cost of destroyed cities in the first line, and print the numbers of destroyed cities in the increasing order in the second line. If there are multiple solutions, you may print any of them.
