DMOPC '17 Contest 2 P3 - Bad Bunnies

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Carrots fear one thing, and one thing alone: bad bunnies.

A lost carrot has found themselves in an unweighted graph with N 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 X and needs to get to node Y to escape. However, there are R rabbits, the ith of which is on node Ri 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:

1RN

1a,b,X,Y,rN

Subtask 1 [20%]

1N1000

Subtask 2 [80%]

1N200000

Input Specification

The first line of input will contain 2 integers, N, and R.
The next N1 lines of input will contain 2 integers each, a, b, indicating there exists an edge between a and b.
The next R lines of input will each contain a single integer, r, indicating that there is a rabbit at r.
The final line of input will contain two integers, X and Y.

Output Specification

A single integer, the closest the carrot will ever get to a rabbit on the path from node X to Y.

Sample Input

Copy
5 1
1 2
1 3
3 4
4 5
5
2 4

Sample Output

Copy
1

Comments

There are no comments at the moment.