题目描述

大象 Dumbo 有一个巨大的迷宫，包含 $n$ 个房间（编号为 $1 \dots n$）和 $n-1$ 条通道，使得从任何一个房间都可以到达其他任何房间。不幸的是，一只老鼠溜进了迷宫。Dumbo 非常害怕老鼠，因此他在房间 $t$ 设置了一个捕鼠器。显然，老鼠会避开有陷阱的房间，所以 Dumbo 必须想出一个更好的策略来诱捕老鼠。老鼠会不停地奔跑，除非它无路可走。Dumbo 还知道，老鼠经过的每一条通道都会留下肮脏的粪便和足迹，老鼠之后会拒绝再次使用这些肮脏的通道。Dumbo 可以清理一条肮脏的通道，或者用石头封锁一条通道。通过封锁或清理通道，他希望迫使老鼠跑进陷阱。他希望以最少的步数完成这一目标，因为他在老鼠面前会感到非常不安。

我们可以将此描述为一个双人游戏。老鼠试图最大化 Dumbo 的步数，而 Dumbo 试图以最少的步数获胜。第一位玩家是 Dumbo。在他的回合中，他可以清理迷宫中的一条肮脏通道，或者封锁一条通道。被封锁的通道是否肮脏并不重要。他不能解封一条通道。然而，他可以选择什么都不做。Dumbo 选择什么都不做的回合不计入步数。当轮到老鼠时，老鼠会选择一条干净且未被封锁的通道，并沿着该通道跑到相邻的房间。如果老鼠当前所在的房间没有这样的通道，老鼠就不会移动。

最初，所有的通道都是干净的，老鼠在房间 $m$，陷阱在房间 $t$，且轮到 Dumbo 行动。如果双方都采取最优策略（老鼠的目标是最大化 Dumbo 的步数），Dumbo 需要的最少步数（清理和封锁通道的总数）是多少？

输入格式

第一行包含整数 $n$、$t$ 和 $m$，用空格分隔。接下来有 $n-1$ 行。每行包含两个整数 $a_i$ 和 $b_i$，用空格分隔，表示房间 $a_i$ 和 $b_i$ 之间有一条通道。

注意：输入规模较大。

数据范围

• $1 \le n, t, m \le 10^6$

子任务

• 子任务 1（20 分）：$n \le 10$
• 子任务 2（25 分）：保证房间 $m$ 和 $t$ 之间存在一条通道。
• 子任务 3（20 分）：$n \le 1000$
• 子任务 4（35 分）：无额外限制。

输出格式

你的程序应该输出 Dumbo 的步数。

样例

输入 1

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

输出 1

4

说明 1

一种可能的方案： Dumbo 封锁房间 4 和 7 之间的通道。 老鼠移动到房间 6。房间 4 和 6 之间的通道现在变脏了。 Dumbo 封锁房间 6 和 8 之间的通道。 老鼠无法移动。 Dumbo 清理房间 4 和 6 之间的通道。 老鼠移动到房间 4。房间 4 和 6 之间的通道变脏了。 Dumbo 封锁房间 2 和 3 之间的通道。 老鼠移动到房间 2。房间 2 和 4 之间的通道变脏了。 Dumbo 什么都不做。 老鼠只能移动到房间 1 并被捕获。

Dumbo 总共进行了 4 步操作。