P17547 [JAG 2026 Summer Camp #2] Tree + 1

You are given a tree with $N$ vertices numbered from $1$ to $N$. Your goal is to visit every vertex of this tree at least once by following the steps below. 1. Choose any two vertices and add an edge connecting them. 2. Choose any one vertex and visit it. 3. Repeat the following action any number of times: choose any one of the vertices adjacent by an edge to the vertex you are currently visiting, and visit that vertex. This action costs $1$. Find the minimum possible total cost required to achieve the goal.

The input consists of one or more test cases. The first line of the input contains an integer $t$ ($1\le t\le 10^5$), the number of test cases. Each of the $t$ test cases is given in the following format: ```text N u_1 v_1 u_2 v_2 ... u_{N-1} v_{N-1} ``` The integer $N$ ($2\le N\le 5\times 10^5$) represents the number of vertices in the given tree. For each integer $i$ ($1\le i\le N-1$), the integers $u_i$ and $v_i$ represent the vertex numbers of the endpoints of the $i$-th edge. The given graph forms a tree. The sum of $N$ over all test cases does not exceed $5\times 10^5$.

For each test case, output the minimum possible total cost required to achieve the goal.

For the first test case, after adding an edge connecting vertices $4$ and $6$, you can start at vertex $1$ and visit the vertices in the order $1\to 2\to 3\to 4\to 6\to 5$, for a total cost of $5$.