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$$$并将其涂成蓝色。