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:
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.
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$$$.
For each test case, output the minimum number of steps to paint all vertices blue.
321 21 251 21 21 31 41 585 47 11 51 88 37 28 63 4
2 8 13
In the first test case, 378QAQ can paint all vertices blue in the following order:
Name |
---|