Mousetrap

Dumbo the elephant has a huge labyrinth with $n$ rooms numbered $1$ through $n$ and $n-1$ passages, arranged so that every room is reachable from every other room. A mouse has sneaked into the labyrinth. Dumbo is terribly afraid of mice, so he sets a mousetrap in room $t$. The mouse avoids the room with the trap, so Dumbo needs a better plan to bait the mouse into it.

The mouse runs around constantly and never stops, unless it has nowhere to move. It leaves a dirty trail of droppings and footprints in every passage it uses, and it refuses to use a dirty passage again. Dumbo can clean a dirty passage, or block a passage with stones. By blocking passages and cleaning them, he wants to force the mouse into the trap. He would like to do this in as few moves as possible, because he feels highly uncomfortable near a mouse.

Describe this as a game for two players. The mouse tries to maximize the number of Dumbo's moves, and Dumbo tries to win in the smallest number of moves. Dumbo goes first. On his turn he may clean one dirty passage of the labyrinth or block one passage. It does not matter whether the blocked passage is clean or dirty. He cannot unblock a passage. He may also choose to do nothing, and a turn in which he does nothing does not count as a move. When it is the mouse's turn, the mouse chooses a clean unblocked passage leading out of its current room and runs to the room on the other side. If no such passage exists, the mouse does not move.

At the start every passage is clean, the mouse is in room $m$, the trap is in room $t$, and it is Dumbo's turn. Both sides play optimally. Find the smallest number of moves, counting passages cleaned and passages blocked, that Dumbo needs.

The first line contains the integers $n$, $t$, and $m$, separated by spaces. Each of the next $n-1$ lines contains two integers $a$ and $b$, separated by a space, meaning that a passage joins room $a$ and room $b$.

Note that the input size is large.

Print the minimum number of Dumbo's moves on one line. If the mouse starts in the room with the trap, that is $m = t$, print $0$.

• $1 \le n \le 10^6$
• $1 \le t \le n$, $1 \le m \le n$

One scenario that finishes the example in four moves:

• Dumbo blocks the passage between rooms $4$ and $7$.
• The mouse moves to room $6$. The passage between rooms $4$ and $6$ is now dirty.
• Dumbo blocks the passage between rooms $6$ and $8$.
• The mouse cannot move.
• Dumbo cleans the passage between rooms $4$ and $6$.
• The mouse moves to room $4$. The passage between rooms $4$ and $6$ is dirty again.
• Dumbo blocks the passage between rooms $2$ and $3$.
• The mouse moves to room $2$. The passage between rooms $2$ and $4$ is now dirty.
• Dumbo does nothing.
• The mouse can only move to room $1$ and gets caught in the trap.

Dumbo made four moves.