Problem E
She Talks to Angel

Fluttershy’s relationship with her pet bunny Angel has hit the skids. Zecora has brewed a solution—literally—that will help them solve their problem and understand each other better.

Figure 1: Illustration by Kyle Coate.

Zecora realized that the problem is each one’s lack of appreciation for the difficulties faced by the other, and so she concocted a body-swapping potion with a spell that will let them live a day in each other’s horseshoes.

Fluttershy and Angel, in each other’s bodies, must complete all the chores in the Sweet Feather Sanctuary. Only after completing all the chores, and experiencing the burdens carried by each other, will the lesson be learned and the spell be lifted.

Sweet Feather Sanctuary is a network of $N$ junctions, labeled $1$ to $N$, connected by $N-1$ paths, such that each path connects two distinct junctions and from any junction it is possible to reach any other junction by treading a series of one or more paths. The $i^\text {th}$ of these paths connects junctions $A_ i$ and $B_ i$, is one kilometer long, and can be traveled in either direction.

There are $C$ chores, labeled $1$ to $C$, that need to be accomplished. The chore labeled $i$ is located at the junction labeled $P_ i$. Note that there can be multiple chores at the same junction.

Sweet Feather Sanctuary is very large, and compared to the amount of time it takes to get around, the time it takes to actually do the chores is negligible. Hence, assume for simplicity that it takes zero time to do a chore. On the other hoof, or paw, Fluttershy travels at the speed of $K$ kilometers per hour, while Angel travels at the speed of $L$ kilometers per hour.

Fluttershy and Angel begin at the central square at the junction labeled $1$. They will first split the chores between themselves, such that both of them get at least one chore and every chore is done by exactly one of them. Then, they will independently go around the sanctuary to do their chores before returning to the central square to express the difficulty of the task and their gratitude for the other.

Fluttershy and Angel are eager to finish the chores as fast as possible and return to their original bodies. How should they split the chores between themselves such that if they both took the optimal route, they would finish the chores and return to the central square as fast as possible? Note that if one of them has finished and arrived at the central square before the other, she or he will have to wait.

Input

The first line of input contains four integers, $N$ ($1 \leq N \leq 4\, 000$), $C$ ($2 \leq C \leq 8\, 000$), $K$ and $L$ ($1 \leq K, L \leq 10^9$), the number of junctions, the number of chores, Fluttershy’s speed in kilometers per hour and Angel’s speed in kilometers per hour, respectively.

The next line of input contains $C$ integers $P_1, P_2, \dots , P_ C$ ($1 \leq P_ i \leq N$), the junctions the chores are located.

The next $N-1$ lines of input contain the descriptions of the paths. In particular, the $i^\text {th}$ of these lines contains two integers $A_ i$ and $B_ i$ ($1 \leq A_ i, B_ i \leq N$; $A_ i \neq B_ i$), denoting that the $i^\text {th}$ path connects junctions $A_ i$ and $B_ i$.

It is guaranteed that from any junction it is possible to reach any other junction by treading a series of one or more paths.

Output

On the first line, output two integers $c_ f$ and $c_ a$ ($1 \leq c_ f, c_ a \leq C-1$; $c_ f + c_ a = C$), the number of chores Fluttershy should do and the number of chores Angel should do, respectively.

On the second line, output $c_ f$ integers $p_1, p_2, \dots , p_{c_ f}$ ($1 \leq p_ i \leq C$), denoting the labels of the chores that Fluttershy should do.

On the third line, output $c_ a$ integers $q_1, q_2, \dots , q_{c_ a}$ ($1 \leq q_ i \leq C$), denoting the labels of the chores that Angel should do.

All $p_ i$ and $q_ i$ should be distinct and partitioning the chores in this way should, among all such partitions, result in the minimum possible time taken, assuming both Fluttershy and Angel take the optimal routes. You can output the chores in any order.

If there are multiple correct answers, you can output any of them.

7 4 7 2
3 4 6 7
1 2
1 3
1 4
1 5
5 6
5 7

3 1
1 3 4
2

10 9 7 2
2 3 4 5 6 7 8 9 10
1 2
1 4
2 3
4 5
5 6
6 7
7 8
8 9
9 10

7 2
3 4 5 6 7 8 9
1 2

4 4 1 1
2 2 3 4
1 2
2 3
1 4

2 2
1 3
2 4