311367: CF1975D. Paint the Tree

D. Paint the Treetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

378QAQ has a tree with $n$ vertices. Initially, all vertices are white.

There are two chess pieces called $P_A$ and $P_B$ on the tree. $P_A$ and $P_B$ are initially located on vertices $a$ and $b$ respectively. In one step, 378QAQ will do the following in order:

1. Move $P_A$ to a neighboring vertex. If the target vertex is white, this vertex will be painted red.
2. Move $P_B$ to a neighboring vertex. If the target vertex is colored in red, this vertex will be painted blue.

Initially, the vertex $a$ is painted red. If $a=b$, the vertex $a$ is painted blue instead. Note that both the chess pieces must be moved in each step. Two pieces can be on the same vertex at any given time.

378QAQ wants to know the minimum number of steps to paint all vertices blue.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\leq t\leq 10^4$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1\leq n\leq 2\cdot 10^5$).

The second line of each test case contains two integers $a$ and $b$ ($1\leq a,b\leq n$).

Then $n - 1$ lines follow, each line contains two integers $x_i$ and $y_i$ ($1 \le x_i,y_i \le n$), indicating an edge between vertices $x_i$ and $y_i$. It is guaranteed that these edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output the minimum number of steps to paint all vertices blue.

ExampleInput

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

Output

2
8
13

Note

In the first test case, 378QAQ can paint all vertices blue in the following order:

• Initially, $P_A$ is located on the vertex $1$, and $P_B$ is located on the vertex $2$. The vertex $1$ is painted red and the vertex $2$ is white.
• 378QAQ moves $P_A$ to the vertex $2$ and paints it red. Then 378QAQ moves $P_B$ to the vertex $1$ and paints it blue.
• 378QAQ moves $P_A$ to the vertex $1$. Then 378QAQ moves $P_B$ to the vertex $2$ and paints it blue.

题目大意：
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≤t≤10^4）。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）。
每个测试用例的第二行包含两个整数a和b（1≤a，b≤n）。
然后是n-1行，每行包含两个整数x_i和y_i（1≤x_i，y_i≤n），表示顶点x_i和y_i之间的边。保证这些边构成一棵树。
保证所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，输出将所有顶点涂成蓝色的最小步数。题目大意： 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≤t≤10^4）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）。 每个测试用例的第二行包含两个整数a和b（1≤a，b≤n）。 然后是n-1行，每行包含两个整数x_i和y_i（1≤x_i，y_i≤n），表示顶点x_i和y_i之间的边。保证这些边构成一棵树。 保证所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出将所有顶点涂成蓝色的最小步数。