鬼抓人

题目描述

有一棵 $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}$

输出格式

输出游戏结束前青木君的移动次数。

样例

5 4 1
1 2
2 3
3 4
3 5

2

双方最优化移动时，游戏按如下方式推进。

• 高桥君移动到顶点 $3$
• 青木君移动到顶点 $2$
• 高桥君移动到顶点 $5$
• 青木君移动到顶点 $3$
• 高桥君移动到顶点 $3$

此时，游戏结束前青木君的移动次数为 $2$ 次。

注意每个回合不能停在同一个顶点。

5 4 5
1 2
1 3
1 4
1 5

1

2 1 2
1 2

0

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

5

数据范围

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