← 返回题目列表

AtCoder · abc148_f

F. 在树上玩标签

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

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

高桥正站在顶点 u,青木站在顶点 v.

现在,他们将玩一场捉人游戏,如下:

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

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

  • 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}

输出

打印 Aoki 在游戏结束前将执行的步数。


示例输入 1

5 4 1
1 2
2 3
3 4
3 5

示例输出 1

2

如果双方都发挥最佳,游戏将按如下方式进行:

  • Takahashi 转至 Vertex 3.
  • 青木转至顶点 2.
  • Takahashi 转至 Vertex 5.
  • 青木转至顶点 3.
  • Takahashi 转至 Vertex 3.

这里,青木执行了两个动作。

注意,每次移动时,禁止停留在当前顶点。


示例输入 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