配点 : $600$ 点

問題文

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

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

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

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

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

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

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

制約

• $2 \leq N \leq 10^5$
• $1 \leq u,v \leq N$
• $u \neq v$
• $1 \leq A_i,B_i \leq N$
• 与えられるグラフは木である

入力

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

$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