Carrots 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