题目描述

$N$ 頂点の木があります。$i$ 番目の辺は頂点 $A_i$ と $B_i$ を双方向に結んでいます。

この木の頂点 $u$ に高橋君が、頂点 $v$ に青木君がいます。

$2$ 人は次のような手順で鬼ごっこをします。

• $1$. 高橋君と青木君が同じ頂点にいるときゲームを終了する。そうでないとき、高橋君は隣接する頂点を $1$ つ選んでその頂点に移動する。
• $2$. 高橋君と青木君が同じ頂点にいるときゲームを終了する。そうでないとき、青木君は隣接する頂点を $1$ つ選んでその頂点に移動する。
• $3$. $1$ に戻る。

高橋君はできるだけ遅くゲームが終了するように移動し、青木君はできるだけ早くゲームが終了するように移動します。

高橋君と青木君が常に互いの位置と戦略を把握し最適に移動するとき、ゲームが終了するまでに青木君が移動する回数を求めてください。

なお、ゲームは必ず終了することが証明できます。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

ゲームが終了するまでに青木君が移動する回数を出力せよ。

题目大意

有一棵$n$个节点的树。$T$站在$u$号节点上，$A$站在$v$号节点上。

现在，两个人轮流移动，$T$是先手。每人每次移动必须移动到任何一个相邻的节点。如果某个人发现自己与对方站在了同一个节点上，那么宣布游戏结束。注意每个人每一轮必须移动。

已知$T$希望游戏能够尽可能晚地结束，$A$希望游戏能够尽可能早地结束。若两人都使用最佳方案，请问$A$会移动多少步？

5 4 1
1 2
2 3
3 4
3 5

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$
• 与えられるグラフは木である

Sample Explanation 1

互いに最適に移動した場合、ゲームは次のように進行します。 - 高橋君が頂点 $3$ に移動 - 青木君が頂点 $2$ に移動 - 高橋君が頂点 $5$ に移動 - 青木君が頂点 $3$ に移動 - 高橋君が頂点 $3$ に移動 このとき、ゲームが終了するまでの青木君の移動回数は $2$ 回です。 各手番で同じ頂点にとどまることは出来ないことに注意してください。