← 返回题目列表

Codeforces · 813/C

C. 标签游戏

中文机器翻译题面 查看原题

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