[CEOI2017] Mousetrap

题目描述

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

输入输出格式

输入格式


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

说明

**样例解释** - 管理者先堵住房间 $4$ 和 $7$ 之间的走廊。 - 老鼠走到房间 $6$。房间 $4$ 和 $6$ 之间的走廊现在是脏的。 - 管理者堵住房间 $6$ 和 $8$ 之间的走廊。 - 老鼠不能动。 - 管理者清理房间 $4$ 和 $6$ 之间的走廊,房间 $4$ 和 $6$ 之间的走廊现在是干净的。 - 老鼠走到房间 $4$,房间 $4$ 和 $6$ 之间的走廊现在是脏的。 - 管理者堵住房间 $2$ 和 $3$ 之间的走廊。 - 老鼠走到房间 $2$,房间 $2$ 和 $4$ 之间的走廊现在是脏的。 - 管理者不进行操作。 - 老鼠走到房间 $1$。 这个过程中管理者总共进行了 $4$ 次操作。 **数据范围** 对于所有的数据,$1 \le n \le 10^6$。