题目描述

罗马帝国正在衰亡。

帝国由 $n$ 个行省构成，并有 $n-1$ 条道路连接这些行省。任意一个行省都可以通过道路到达任意另一个行省，因此这些道路构成一棵树。

两个蛮族部落已经分别占领了两个不同的行省：一个由西哥特人控制，另一个由东哥特人控制。

从此以后，每一年中：

每一个已经被蛮族占领的行省，都可以发动一次军事行动，并占领一个与它相邻且尚未被占领的行省。

这些行动可以在同一年并行发生。

求最少经过多少年，可以让整个帝国的所有行省都被占领。

输入格式

第一行包含三个整数 $n,p,q$：

• $2\le n\le300000$；
• $1\le p,q\le n$；
• $p\ne q$。

其中 $p$ 和 $q$ 是最初已经被两个蛮族部落占领的行省。

接下来 $n-1$ 行，每行包含两个整数 $a,b$，表示行省 $a$ 与 $b$ 之间有一条道路。

保证所给图是一棵树。

输出格式

输出一个整数，表示占领全部行省所需的最少年数。

样例

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

3

样例说明

最初占领的是行省 $2$ 与 $3$。

• 第 $1$ 年：行省 $3$ 占领 $1$，行省 $2$ 占领 $4$；
• 第 $2$ 年：行省 $1$ 占领 $5$；
• 第 $3$ 年：行省 $1$ 占领 $6$。

因此最少需要 $3$ 年。

子任务

这里的毛毛虫树是指：删除所有叶子后，剩余图是一条路径。在本子任务中，可理解为由路径 $p\leftrightarrow q$ 加上一些额外叶子构成，并且这些额外点均连接到该路径上除 $p,q$ 外的内部顶点。