Alice 厌倦了按照通常的规则玩标签游戏,所以她向 Bob 提供了一些修改。现在游戏应该在 n 个顶点的无向有根树上进行。顶点 1 是树的根。
Alice 从顶点 1 开始,Bob 从顶点 x (x ≠ 1) 开始。动作是轮流进行的,鲍勃先行。在一次移动中,一个人可以停留在当前顶点,也可以移动到相邻的顶点。
当爱丽丝到达鲍勃所站的同一顶点时,游戏结束。爱丽丝想要最小化总移动次数,而鲍勃想要最大化它。
您应该编写一个程序来确定游戏将持续多少步。
输入
第一行包含两个整数 n 和 x (2 ≤ n ≤ 2·105, 2 ≤ x ≤ n)。
接下来的 n - 1 行中的每一行都包含两个整数 a 和 b (1 ≤ a, b ≤ n) — 树的边。保证边形成有效的树。
输出
打印 Alice 和 Bob 将进行的总移动次数。
示例
输入 #1
4 3 1 2 2 3 2 4
输出 #1
4
输入 #2
5 2 1 2 2 3 3 4 2 5
输出 #2
6
注意
在第一个示例中,树如下所示:
红色顶点是 Alice 的起始位置,蓝色顶点是 Bob 的起始位置。鲍勃在整个游戏过程中都会站在顶点 3,从而使游戏运行时间最长。因此,动作如下:
B:停留在顶点 3
A:转到顶点 2
B:停留在顶点 3
A:转到顶点 3
在第二个示例中,树如下所示:
最优策略的动作是:
B:转到顶点 3
A:转到顶点 2
B:转到顶点 4
A:转到顶点 3
B:停留在顶点 4
A:转到顶点 4