CF1830A.Copil Copac Draws Trees

Copil Copac is given a list of $n-1$ edges describing a tree of $n$ vertices. He decides to draw it using the following algorithm:

• Step $0$: Draws the first vertex (vertex $1$). Go to step $1$.
• Step $1$: For every edge in the input, in order: if the edge connects an already drawn vertex $u$ to an undrawn vertex $v$, he will draw the undrawn vertex $v$ and the edge. After checking every edge, go to step $2$.
• Step $2$: If all the vertices are drawn, terminate the algorithm. Else, go to step $1$.

The number of readings is defined as the number of times Copil Copac performs step $1$.

Find the number of readings needed by Copil Copac to draw the tree.

科皮尔·科帕克得到了一个包含 $n-1$ 条边的列表，这些边描述了一棵具有 $n$ 个顶点的树。他决定使用以下算法来绘制这棵树：

• 步骤 0：绘制第一个顶点（顶点 $1$）。然后进入步骤 1。
• 步骤 1：按输入中边的顺序，依次检查每条边：若某条边连接了一个已绘制的顶点 $u$ 与一个未绘制的顶点 $v$，则他将绘制该未绘制的顶点 $v$ 及这条边。在检查完所有边后，进入步骤 2。
• 步骤 2：若所有顶点均已绘制，则算法终止；否则，返回步骤 1。

定义“读取次数”为科皮尔·科帕克执行步骤 1 的总次数。

求科皮尔·科帕克绘制该树所需的读取次数。

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

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices of the tree.

The following $n - 1$ lines of each test case contain two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$) — indicating that $(u_i,v_i)$ is the $i$-th edge in the list. 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 $2 \cdot 10^5$.

每个测试包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示树的顶点数。

每个测试用例接下来的 $n - 1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，且 $u_i \neq v_i$），表示列表中的第 $i$ 条边为 $(u_i,v_i)$。保证所给边构成一棵树。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, output the number of readings Copil Copac needs to draw the tree.

对于每个测试用例，输出 Copil Copac 为绘制该树所需的读数个数。

In the first test case:

After the first reading, the tree will look like this:

After the second reading:

Therefore, Copil Copac needs $2$ readings to draw the tree.

在第一个测试用例中：

第一次读取后，树将如下所示：

第二次读取后：

因此，Copil Copac 需要 $2$ 次读取来绘制该树。