Cow at Large

题目描述:

由于Bessie犯了错误，躲避到一个偏远的农场，FJ得知此事之后带领众多守卫前来抓捕。

农场由 N 个谷仓和 N-1 条无向的边相连接，使每对谷仓之间有一条唯一的路径可达。每个只有一条边相连接的谷仓就是一个出口。当清晨来临时，Bessie将出现在一个谷仓中，并尝试到达出口处--逃跑。

但是，Bessie想要逃跑可没那么容易，FJ在这个农场安放了很多个守卫来抓捕Bessie。然而所有的守卫都将被安放在各出口的谷仓，并试图抓住Bessie。守卫的移动速度与Bessie相同（所以在每个时间段，Bessie或者每个守卫可以从一个谷仓移动到相邻的谷仓）。守卫们知道Bessie在哪里，同样Bessie也知道守卫在哪里。如果守卫在任何时候与Bessie在同一个谷仓或者同一条边相遇时，守卫就会抓住Bessie。相反，如果Bessie在守卫赶到出口之前到达出口谷仓，它就成功逃跑了。

Bessie不确定自己是否可以成功逃脱，这取决于FJ部署的守卫数量。初始的时候Bessie在编号为K的谷仓中，请帮助FJ确定捕捉Bessie需要的守卫的最小数量，假设守卫在出口谷仓中自我分配最佳。

输入格式:

第 1 行包含 N 和K。

第 2 到第 N 行，每行包含两个整数u和v，表示谷仓u和v相连接。

输出格式:

输出共一行一个整数，即确保捕捉Bessie所需的最少数量的守卫。

样例输入:

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

样例输出:

3

提示:

对于100%的数据：2≤N≤100,000；1≤K≤N；1≤u≠v≤N；

时间限制: 1000ms
空间限制: 128MB

---

来源: Usaco2018 Jan Gold