Olimpiada Informatyczna
|
XI Olimpiad in Informatics 2003/2004
|
Task: WSC
East-West
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?
Task
Your task is to write a programme which:
-
reads from the standard input a description of the railway network and border
checkpoints at which the waste-carrying trains have arrived,
-
finds the minimal number of days the transit has to last,
-
writes the solution to the standard output.
Input
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.
Output
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.
Example
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 2
the correct outcome is:
4
|
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.
|