← 返回题目列表

Codeforces · 1975/D

D. 画树

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

378QAQ有一棵有$$$n$$$个顶点的树。最初,所有顶点都是白色的。

树上有两个棋子,分别为$$$P_A$$$ 和$$$P_B$$$。 $$$P_A$$$ 和 $$$P_B$$$ 最初分别位于顶点 $$$a$$$ 和 $$$b$$$ 上。第一步,378QAQ 将按顺序执行以下操作:

1. 将 $$$P_A$$$ 移动到相邻顶点。如果目标顶点是白色,则该顶点将被涂成红色。
2. 将 $$$P_B$$$ 移动到相邻顶点。如果目标顶点为红色,则该顶点将被涂成蓝色。

最初,顶点 $$$a$$$ 被涂成红色。如果$$$a=b$$$,则顶点$$$a$$$ 被涂成蓝色。请注意,每一步都必须移动两个棋子。在任何给定时间,两个部分都可以位于同一顶点。

378QAQ 想知道将所有顶点涂成蓝色的最少步骤数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\leq t\leq 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$)。

每个测试用例的第二行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1\leq a,b\leq n$$$)。

接下来是 $$$n - 1$$$ 行,每行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i,y_i \le n$$$),表示顶点 $$$x_i$$$ 和 $$$y_i$$$ 之间的一条边。保证这些边形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出将所有顶点绘制为蓝色的最小步骤数。

示例

输入 #1

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

输出 #1

2
8
13

注意

在第一个测试用例中,378QAQ 可以按以下顺序将所有顶点绘制为蓝色:

- 最初,$$$P_A$$$ 位于顶点 $$$1$$$ 上,$$$P_B$$$ 位于顶点 $$$2$$$ 上。顶点 $$$1$$$ 被涂成红色,顶点 $$$2$$$ 被涂成白色。
- 378QAQ 将 $$$P_A$$$ 移动到顶点 $$$2$$$ 并将其涂成红色。然后378QAQ将$$$P_B$$$移动到顶点$$$1$$$并将其涂成蓝色。
- 378QAQ 将 $$$P_A$$$ 移动到顶点 $$$1$$$。然后378QAQ将$$$P_B$$$移动到顶点$$$2$$$并将其涂成蓝色。