F - Playing Tag on Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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}

出力

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

入力例 1

5 4 1
1 2
2 3
3 4
3 5

出力例 1

2

互いに最適に移動した場合、ゲームは次のように進行します。

  • 高橋君が頂点 3 に移動
  • 青木君が頂点 2 に移動
  • 高橋君が頂点 5 に移動
  • 青木君が頂点 3 に移動
  • 高橋君が頂点 3 に移動

このとき、ゲームが終了するまでの青木君の移動回数は 2 回です。

各手番で同じ頂点にとどまることは出来ないことに注意してください。

入力例 2

5 4 5
1 2
1 3
1 4
1 5

出力例 2

1

入力例 3

2 1 2
1 2

出力例 3

0

入力例 4

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

出力例 4

5

Score : 600 points

Problem Statement

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.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq u,v \leq N
  • u \neq v
  • 1 \leq A_i,B_i \leq N
  • The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of moves Aoki will perform before the end of the game.

Sample Input 1

5 4 1
1 2
2 3
3 4
3 5

Sample Output 1

2

If both players play optimally, the game will progress as follows:

  • Takahashi moves to Vertex 3.
  • Aoki moves to Vertex 2.
  • Takahashi moves to Vertex 5.
  • Aoki moves to Vertex 3.
  • Takahashi moves to Vertex 3.

Here, Aoki performs two moves.

Note that, in each move, it is prohibited to stay at the current vertex.

Sample Input 2

5 4 5
1 2
1 3
1 4
1 5

Sample Output 2

1

Sample Input 3

2 1 2
1 2

Sample Output 3

0

Sample Input 4

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

Sample Output 4

5