题目描述

We have a tree with $N$ vertices. The $i$-th edge connects Vertex $A_i$ and $B_i$ bidirectionally.

Takahashi is standing at Vertex $u$, and Aoki is standing at Vertex $v$.

Now, they will play a game of tag as follows:

• $1$. If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Takahashi moves to a vertex of his choice that is adjacent to his current vertex.

• $2$. If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Aoki moves to a vertex of his choice that is adjacent to his current vertex.

• $3$. Go back to step $1$.

Takahashi performs his moves so that the game ends as late as possible, while Aoki performs his moves so that the game ends as early as possible.

Find the number of moves Aoki will perform before the end of the game if both Takahashi and Aoki know each other's position and strategy.

It can be proved that the game is bound to end.

我们有一棵有 $N$ 个顶点的树。第 $i$ 条边双向连接顶点 $A_i$ 和 $B_i$ 。

高桥站在顶点 $u$ ，青木站在顶点 $v$ 。

现在，他们将进行如下的捉人游戏：

• $1$ .如果高桥和青木站在同一个顶点，游戏结束。否则，高桥移动到他选择的与当前顶点相邻的顶点。

• $2$ .如果高桥和青木站在同一顶点，对局结束。否则，青木移动到自己选择的与当前顶点相邻的顶点。

• $3$ .回到步骤 $1$ 。

高桥的下法是尽可能晚地结束对局，而青木的下法是尽可能早地结束对局。

如果高桥和青木都知道对方的位置和策略，求青木在对局结束前要下的步数。

可以证明对局必将结束。

输入格式

输入内容按以下格式标准输入：

$N$ $u$ $v$
$A_1$ $B_1$
$:$
$A_{N-1}$ $B_{N-1}$

输出格式

打印青木在对局结束前要走的步数。

样例 #1

样例输入 #1

5 4 1
1 2
2 3
3 4
3 5

样例输出 #1

2

样例 #2

样例输入 #2

5 4 5
1 2
1 3
1 4
1 5

样例输出 #2

1

样例 #3

样例输入 #3

2 1 2
1 2

样例输出 #3

0

样例 #4

样例输入 #4

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

样例输出 #4

5

说明

数据规模与约定

• $2 \leq N \leq 10^5$
• $1 \leq u,v \leq N$
• $u \neq v$
• $1 \leq A_i,B_i \leq N$
• 给定图形是一棵树。

样例 $1$ 解释

如果两位棋手都以最佳状态下棋，棋局的进展情况如下：

• 高桥走到顶点 $3$ 。
• 青木移至顶点 $2$ 。
• 高桥(Takahashi)下到顶点 $5$ 。
• 青木移动到顶点 $3$ 。
• 高桥移动到顶点 $3$ 。

在这里，青木下了两步棋。

需要注意的是，每一步都禁止停留在当前顶点。