DMOPC '17 Contest 2 P3 - Bad Bunnies
View as PDFCarrots fear one thing, and one thing alone: bad bunnies.
A lost carrot has found themselves in an unweighted graph with  nodes inside bad bunny territory. The carrot knows a little graph theory and recognizes that this graph is a tree! Currently, they are at node 
 and needs to get to node 
 to escape. However, there are 
 rabbits, the 
 of which is on node 
 of the graph. Help this carrot figure out the closest they will ever have to be to a rabbit during their escape.
Constraints
For all test cases:
Subtask 1 [20%]
Subtask 2 [80%]
Input Specification
The first line of input will contain 2 integers, , and 
.
The next  lines of input will contain 2 integers each, 
, 
, indicating there exists an edge between 
 and 
.
The next  lines of input will each contain a single integer, 
, indicating that there is a rabbit at 
.
The final line of input will contain two integers,  and 
.
Output Specification
A single integer, the closest the carrot will ever get to a rabbit on the path from node  to 
.
Sample Input
5 1
1 2
1 3
3 4
4 5
5
2 4
Sample Output
1
Comments