2015
04-13

# East and West

TDB (Tie Dao Bu) is a magical department in TC (Tian Chao), as you all know… Now we have some emergency foods to transport from east TC to west TC. In order to avoid more tragedies, this time it’s your turn to act as the role of scheduling the trains…
There are N stations numbered from 1 to N in TC, connected by M undirected railways, guaranteeing that any of the two stations are reachable to each other.
The east of TC has E (numbered from 1 to E) stations, while the west has W (numbered from N-W+1 to N) stations. Initially, P trains filled with food are waiting at P different stations in the east. Your task is to schedule these trains, thus making them finally stopped at P different stations in the west.
Here, the time for a train to pass a single railway is exactly one day. And for safety reasons, each railway can let only one train pass per day. Moreover, a train can stop at any station for an arbitrarily number of days. And each station can hold at most P trains.
To simplify, we shall promise that M = N – 1 and N <= 10^6, and there always exists a railway whose removal separates the east and the west.
Your task is to make the trains’ arrival completed as soon as possible.

There are multiple test cases. For each test case, there will be 4 integers in the first line, namely N, M, E and W, as mentioned above. Each of the next M lines will contain two integers u and v, which indicates a railway between u and v. Then the following line has a single integer P. For the next P lines, each will contain a single integer describing the initial positions for the trains with food.

There are multiple test cases. For each test case, there will be 4 integers in the first line, namely N, M, E and W, as mentioned above. Each of the next M lines will contain two integers u and v, which indicates a railway between u and v. Then the following line has a single integer P. For the next P lines, each will contain a single integer describing the initial positions for the trains with food.

2 1 1 1
1 2
1
1

1

,