34590번 - Gamer Bafuko 다국어

문제

Bafuko loves gaming! She is currently playing the latest title, Young Bracelet – Light of the Saint Grass. As an experienced gamer, she wants to explore every location on the map.

The map can be represented as a tree with n vertices numbered from 1ドル$ to $n$. Each edge of the tree has weight 1ドル$. In addition, there is a special portal connecting two designated distinct vertices $x$ and $y$. This portal can be used any number of times and allows instantaneous travel between $x$ and $y$ at zero cost.

Bafuko wants to visit every vertex of the tree at least once by following a tour. A tour is a sequence of adjacent vertices that begins at a chosen vertex, ends at a chosen vertex (possibly the same one), and visits every vertex of the tree at least once. She may freely choose the starting and ending vertices. During the tour, both edges and the portal may be traversed multiple times if necessary. The cost of the tour is defined as the sum of the costs of all traversed edges and portal uses, where repeated traversals are counted multiple times.

Your task is to determine the minimum total cost of such a tour.

입력

Each test contains multiple test cases. The first line contains the number of test cases $t$. The description of the test cases follows.

The first line of each test case contains three integers $n,ドル $x,ドル and $y,ドル representing the number of vertices in the tree and the two vertices connected by the portal.

Followed by $n − 1$ lines, the $i$-th of which contains two integers $u_i,ドル $v_i,ドル representing an edge between vertices $u_i$ and $v_i$.

출력

For each test case, print a single integer in a new line, representing the minimum total cost of a tour that visits every vertex of the tree at least once.

제한

• 1ドル ≤ t ≤ 10^4$
• 2ドル ≤ n ≤ 5 \times 10^5$
• 1ドル ≤ x, y ≤ n$ and $x \ne y$.
• 1ドル ≤ u_i , v_i ≤ n$ and $u_i \ne v_i$.
• It is guaranteed that the given edges form a tree.
• It is guaranteed that the sum of $n$ over all test cases does not exceed 5ドル \times 10^5$.

노트