You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 $Y$ 和小 $N$ 在博弈。给定一棵 $n$ 个点的树，树上有一个特殊节点 $T$ ，在游戏中，小 $N$ 会从树上的节点 $S$ 出发，一旦小 $N$ 到达 $T$ 则游戏结束。

小 $N$ 每次经过一条边就会损坏掉这条边，每一轮，小 $Y$ 可以做如下 $3$ 个操作中的一个：

• 不操作（不计入小 $Y$ 的操作总次数）

• 断掉一条边

• 修复一条损坏的边（注意只能是小 $N$ 导致的损坏边，不能修复小 $Y$ 自己断掉的边）

小 $N$ 每一轮的操作如下：

• 如果小 $N$ 所在节点不存在完好的出边则不进行操作。

• 否则选择一条出边走过去，不能不走。

小 $Y$ 先开始操作，随后两人交替进行操作。小 $Y$ 希望游戏结束时自己的操作总次数尽量少，小 $N$ 则希望小 $Y$ 的操作总次数尽量多。

假设两人都绝顶聪明，按最优策略行动，询问最终小 $Y$ 的操作总次数。

输入格式

第一行三个整数 $n, T, S$。接下来 $n - 1$ 行，第 $i$ 行两个整数 $u_i, v_i$ 表示树上存在边 $(u_i, v_i)$。

输出格式

一行一个整数表示答案。

样例输入1

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

样例输出1

4

【样例 2】

参见下发文件。

数据规模和约定

本题开启捆绑测试。对于所有数据，有 $1 \leq n \leq 10^6$, $1 \leq u_i, v_i \leq n$。输入文件较大，请选手注意代码的输入效率。

样例解释

小 $Y$ 断开 $4$ 与 $7$ 之间的边。

小 $N$ 走到 $6$ ， $4$ 与 $6$ 之间的边现在是损坏的。

小 $Y$ 断开 $6$ 与 $8$ 之间的边。

小 $N$ 不能动。

小 $Y$ 修复 $4$ 与 $6$ 之间的边。

小 $N$ 走到 $4$ ， $4$ 与 $6$ 之间的边现在是损坏的。

小 $Y$ 断开 $2$ 与 $3$ 之间的边。

小 $N$ 走到 $2$ ， $4$ 与 $2$ 之间的边现在是损坏的。

小 $Y$ 不操作。

小 $N$ 走到 $1$ 。

总操作数 $4$ 次。