XI Olimpiad in Informatics 2003/2004
|III stage competition|
|Memory limit:||256 MB|
International agreements signed by the Awfully Vast State impose
on it transit obligations - it has to enable the transport of nuclear waste from its eastern
neighbours power plants to recycling facilities in the West, by means of its railway system.
Ecological reasons impose such traffic organization, that the waste-carrying trains leave
the territory of the state as quickly as possible.
The railway network in this country has a very peculiar structure. It consists of n cities - railway junctions and n-1 two-way railway track segments, connecting the junctions. Transport is possible between each pair of cities. Furthermore, there is a section of the railway track, whose ends are not border cities and every connection from the eastern to the western border has to lead through that very section.
All waste-carrying trains arrive at the eastern border on the same day, before dawn, at distinct checkpoints, however. For safety reasons the trains only move during the day. Only a single waste-carrying train can move on a given track section at a time, but an unlimited amount of them can wait at a junction. It takes one day for a train to traverse a section of the track. The traffic has to be organized in such a way, that allows each waste-carrying train to reach a distinct destination on the western border.
How many days, at least, do the waste-carrying trains have to spend on the territory of the Awfully Vast State?
Your task is to write a programme which:
The first line of the input contains three integers
1 < n, w, z < 106, n >= w+z+2,
separated by single spaces. n denotes the number of junctions
(which are labelled with 1,...,n), while w and z
denote the number of border checkpoints on the eastern and western border, respectively.
The checkpoints on the eastern border are labelled with
1,...,w, while those on the western border with n-z+1,...,n.
In the following n-1 lines there is a decription of the railway network. Each line contains two distinct integers, 1 < a,b < n, separated by a single space. They denote junctions connected by a section of the railway.
The n+1st line contains a single integer p, 1 < p < w, 1 < p < z, denoting the number of waste-carrying trains. In the next (and last) line of the input there are p distinct integers, all of which are not greater than w, separated by single spaces. These are the numbers of checkpoints on the eastern border, at which the waste-carrying trains have arrived.
The first and only line of the output should contain exactly one integer, denoting
the minimal amount of days the waste have to spend on the territory of the state.
For the input data:
9 2 3 1 3 2 3 4 3 4 5 4 6 7 4 5 8 9 6 2 1 2the correct outcome is:
The arrows denote the movement of the trains in consecutive days for one of the optimal organizations of the railway traffic - a loop means that on a given day the train waited at the junction.