CF1905B.Begginer's Zelda

You are given a tree$^{\dagger}$. In one zelda-operation you can do follows:

• Choose two vertices of the tree $u$ and $v$;
• Compress all the vertices on the path from $u$ to $v$ into one vertex. In other words, all the vertices on path from $u$ to $v$ will be erased from the tree, a new vertex $w$ will be created. Then every vertex $s$ that had an edge to some vertex on the path from $u$ to $v$ will have an edge to the vertex $w$.

Illustration of a zelda-operation performed for vertices $1$ and $5$.

Determine the minimum number of zelda-operations required for the tree to have only one vertex.

$^{\dagger}$A tree is a connected acyclic undirected graph.

给你一棵树$^{\dagger}$。一次“塞尔达操作”（zelda-operation）可执行如下步骤：

• 选择树中的两个顶点 $u$ 和 $v$；
• 将 $u$ 到 $v$ 路径上的所有顶点压缩为一个顶点。换言之，$u$ 到 $v$ 路径上的所有顶点将从树中被删除，并创建一个新顶点 $w$；随后，每个原本与该路径上某个顶点相邻的顶点 $s$，都将改为与新顶点 $w$ 相邻。

对顶点 $1$ 和 $5$ 执行一次塞尔达操作的示意图。

求使整棵树最终仅剩一个顶点所需的最少塞尔达操作次数。

$^{\dagger}$ 树是指一个连通的、无环的无向图。

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

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

$i$-th of the next $n − 1$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n, u_i \ne v_i$) — the numbers of vertices connected by the $i$-th edge.

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 $10^5$.

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

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

接下来的 $n - 1$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n,\; u_i \ne v_i$），表示第 $i$ 条边所连接的两个顶点的编号。

保证给定的边构成一棵树。

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

For each test case, output a single integer — the minimum number of zelda-operations required for the tree to have only one vertex.

对于每个测试用例，输出一个整数——使树最终仅剩一个顶点所需的最少 zelda-操作次数。

In the first test case, it's enough to perform one zelda-operation for vertices $2$ and $4$.

In the second test case, we can perform the following zelda-operations:

1. $u = 2, v = 1$. Let the resulting added vertex be labeled as $w = 10$;
2. $u = 4, v = 9$. Let the resulting added vertex be labeled as $w = 11$;
3. $u = 8, v = 10$. After this operation, the tree consists of a single vertex.

在第一个测试用例中，对顶点 $2$ 和 $4$ 执行一次 zelda-操作即可。

在第二个测试用例中，我们可以执行以下 zelda-操作：

1. $u = 2, v = 1$，将新添加的顶点标记为 $w = 10$；
2. $u = 4, v = 9$，将新添加的顶点标记为 $w = 11$；
3. $u = 8, v = 10$，该操作完成后，树仅包含一个顶点。