题目描述

有一个有 $n$ 个房间和 $n-1$ 条走廊的迷宫，保证任意两个房间可以通过走廊互相到达，换句话说，这个迷宫的结构是一棵树。
一个老鼠被放进了迷宫，迷宫的管理者决定和老鼠做个游戏。
一开始，有一个房间被放置了陷阱，老鼠出现在另一个房间。老鼠可以通过走廊到达别的房间，但是会弄脏它经过的走廊。老鼠不愿意通过脏的走廊。
每个时刻，管理者可以进行一次操作：堵住一条走廊使得老鼠不能通过，或者擦干净一条走廊使得老鼠可以通过。然后老鼠会通过一条干净的并且没被堵住的走廊到达另一个房间。只有在没有这样的走廊的情况下，老鼠才不会动。一开始所有走廊都是干净的。管理者不能疏通已经被堵住的走廊。
现在管理者希望通过尽量少的操作将老鼠赶到有陷阱的房间，而老鼠则希望管理者的操作数尽量多。请计算双方都采取最优策略的情况下管理者需要的操作数量。
注意：管理者可以选择在一些时刻不操作。

输入格式

第一行三个空格隔开的正整数数 $n,t,m$。分别代表房间的个数，陷阱房的编号和老鼠起始房间的编号。
接下来 $n-1$ 行，每行两个空格隔开的整数 $a_i,b_i$，表示有一条走廊连接编号为 $a_i$ 和 $b_i$ 的房间。

输出格式

输出一行包含一个整数，表示双方都采取最优策略的情况下，管理者需要的操作数量。

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

4

数据范围与提示

• 子任务 1（$20\%$）: $1\le n\le 10$；
• 子任务 2（$25\%$）: $1\le n\le 10^6$，保证老鼠的起始位置和陷阱房相邻；
• 子任务 3（$20\%$）: $1\le n\le 1000$；
• 子任务 4（$35\%$）: $1\le n\le 10^6$。