该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一棵树，包含 n 个结点，编号为 1 ~ n。

一只蚂蚁被放在了编号为 s 的结点上。

一块诱饵被放在了编号为 t （t≠s）的数据的结点上。

‌蚂蚁可以通过树上的边从当前所在结点到达另一个结点。蚂蚁在行进过程中，会从腹部的腺体分泌“信息素”，持续涂抹在经过的路上，形成一条“气味轨迹”。蚂蚁不会经过有“气味”的树边。

小明正在观察这只蚂蚁。在每个时刻，小明最多可以进行一次操作，操作可能为以下两种操作之一：

• 删掉一条树边；
• 将一条有“气味”的树边进行“除味”，使得蚂蚁可以再次通过。

当然，在某个时刻，小明也可以不进行任何操作，只是在观察蚂蚁的动向。

蚂蚁经过一条边需要花费一个时刻的时间。如果蚂蚁位于某个结点时有边可行，它就一定会选择一条可行边爬行，否则它就会待在原地不动。

我们将每个时刻小明的操作或不操作，以及蚂蚁的爬行和不动都称之为“行为”。两者的行为是按时刻交替进行的，小明首先作出行为，即：第一个时刻，小明作出行为，第二个时刻，蚂蚁作出行为，第三个时刻，小明作出行为，依此类推。

小明希望通过尽可能少的操作次数，使得蚂蚁到达有诱饵的结点。蚂蚁则希望小明的操作次数尽可能多。

假设小明和蚂蚁都足够聪明，问：小明最少需要操作多少次？

输入格式

第一行：三个整数 $n,t,s$;

接下来 $n-1$ 行：每行两个整数 $x, y$，表示点 $x$ 和点 $y$ 之间有一条边。

输出格式

一个整数，表示小明使得蚂蚁到达诱饵结点需要的最少操作次数。

样例输入

7 3 4
1 2
2 3
2 4
4 5
4 6
6 7

样例输出

3

样例解释

操作方案可能不唯一，以下是一种可能的操作方案：

时刻 1：小明进行第 1 次操作：删除 (4,6)

时刻 2：蚂蚁会经过 (4,5)，到达 5 号点

时刻 3：小明进行第 2 次操作：清除 (4,5) 的“气味”

时刻 4：蚂蚁会经过 (5,4)，到达 4 号点

时刻 5：小明进行第 3 次操作：删除 (1,2)

此后小明不再进行操作，蚂蚁则会一只爬行直到诱饵结点 3 号点

另一种可能方案如下：

时刻 1：小明进行第 1 次操作：删除 (4,6)

时刻 2：蚂蚁会经过 (4,5)，到达 5 号点

时刻 3：小明进行第 2 次操作：删除 (1,2)

时刻 4：蚂蚁不动

时刻 5：小明进行第 3 次操作：清除 (4,5) 的“气味”

此后小明不再进行操作，蚂蚁则会一只爬行直到诱饵结点 3 号点

数据范围

20% 的数据: 1 ≤ n ≤ 10；

另有 25% 的数据: 1 ≤ n ≤ 10^6，数据保证点 s 与点 t 之间有一条边；

另有 20% 的数据: 1 ≤ n ≤ 1000；

另有 35% 的数据: 1 ≤ n ≤ 10^6。