F - 在树上玩游戏标签

得分：$600$ 分

问题描述

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

Takahashi 站在顶点 $u$ 上，Aoki 站在顶点 $v$ 上。

现在，他们将进行如下的标签游戏：

• $1$. 如果 Takahashi 和 Aoki 站在同一个顶点上，游戏结束。否则，Takahashi 移动到他当前顶点相邻的顶点。

• $2$. 如果 Takahashi 和 Aoki 站在同一个顶点上，游戏结束。否则，Aoki 移动到他当前顶点相邻的顶点。

• $3$. 回到步骤 $1$。

Takahashi 为了让游戏尽量晚结束而选择他的移动，而 Aoki 为了让游戏尽早结束而选择他的移动。

找出在游戏结束前 Aoki 的移动次数，假设 Takahashi 和 Aoki 都知道对方的位置和策略。

可以证明游戏一定会结束。

约束

• $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 在游戏结束前的移动次数。

5 4 1
1 2
2 3
3 4
3 5

2

如果两位玩家都采取最优策略，游戏将会如下进行：

• Takahashi 移动到顶点 $3$。
• Aoki 移动到顶点 $2$。
• Takahashi 移动到顶点 $5$。
• Aoki 移动到顶点 $3$。
• Takahashi 移动到顶点 $3$。

在这里，Aoki 进行了两次移动。

请注意，每次移动时，不允许停留在当前顶点。

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