Description

There is a maze with $n$ rooms and $n-1$ corridors. It is guaranteed that any two rooms are connected by corridors; in other words, the maze structure is a tree.

A mouse is put into the maze, and the maze manager decides to play a game with the mouse.

At the beginning, one room contains a trap, and the mouse appears in another room. The mouse can move to other rooms through corridors, but it will dirty every corridor it passes through. The mouse does not want to go through dirty corridors.

At each moment, the manager may perform one operation: block a corridor so that the mouse cannot pass through it, or clean a corridor so that the mouse can pass through it. Then the mouse will move through one corridor that is clean and not blocked to another room. Only if there is no such corridor will the mouse stay still. Initially, all corridors are clean. The manager cannot unblock a corridor once it has been blocked.

Now the manager wants to drive the mouse into the room with the trap using as few operations as possible, while the mouse wants the manager to use as many operations as possible. Compute the number of operations the manager needs when both sides play optimally.

Note: The manager may choose to do nothing at some moments.

Input Format

The first line contains three space-separated positive integers $n,t,m$, representing the number of rooms, the index of the trap room, and the index of the mouse’s starting room.

The next $n-1$ lines each contain two space-separated integers $a_i,b_i$, meaning there is a corridor connecting rooms $a_i$ and $b_i$.

Output Format

Output one line containing one integer, indicating the number of operations the manager needs when both sides play optimally.

10 1 4
1 2
2 3
2 4
3 9
3 5
4 7
4 6
6 8
7 10

4

Hint

Sample Explanation

• The manager first blocks the corridor between rooms $4$ and $7$.
• The mouse moves to room $6$. The corridor between rooms $4$ and $6$ is now dirty.
• The manager blocks the corridor between rooms $6$ and $8$.
• The mouse cannot move.
• The manager cleans the corridor between rooms $4$ and $6$. The corridor between rooms $4$ and $6$ is now clean.
• The mouse moves to room $4$. The corridor between rooms $4$ and $6$ is now dirty.
• The manager blocks the corridor between rooms $2$ and $3$.
• The mouse moves to room $2$. The corridor between rooms $2$ and $4$ is now dirty.
• The manager performs no operation.
• The mouse moves to room $1$.

In this process, the manager performed a total of $4$ operations.

Constraints

For all testdata, $1 \le n \le 10^6$.

Translated by ChatGPT 5