分数: 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