Minimum Moves for Robot Obstacle Navigation on a Tree

A robot, Rob, is located on a tree structured path \(T\). There are several movable obstacles placed on some vertices of \(T\). No vertex can contain more than one object at any moment. At each move, you can move either the robot or one obstacle to an adjacent vertex provided that the target vertex is empty.

You are given the tree \(T\) (with \(n\) vertices and \(n-1\) edges), a starting vertex \(s\) where the robot is located, a target vertex \(t\) where the robot must go, and the initial positions of \(k\) obstacles (the obstacles are identical). Move the objects (robot and obstacles) so that the robot reaches \(t\) in the minimum number of moves.

Note: The obstacles can be moved arbitrarily as long as you follow the move rules. If it is impossible to get the robot to \(t\), output \(-1\).

Input formula summary:
The tree \(T\) is given by its edges, and the moves are defined as moving any object (robot or obstacle) one step along an edge into a vacant vertex.

inputFormat

The input is given as follows:

 n
 u1 v1
 u2 v2
 ...
 u(n-1) v(n-1)
 s t
 k
 p1 p2 ... pk

Where:

• n is the number of vertices in the tree (vertices are numbered 1 through n).
• Each of the next n-1 lines contains two integers u and v representing an edge between vertices u and v.
• s and t are the starting and target vertices of the robot.
• k is the number of obstacles.
• The next line contains k integers, representing the vertices initially occupied by obstacles. It is guaranteed that s and t are not occupied by obstacles.

outputFormat

Output a single integer: the minimum number of moves required for the robot to reach vertex t. If it is impossible, output -1.

sample

3
1 2
2 3
1 3
1
2

-1