East and West
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.
2 1 1 1 1 2 1 1