题目描述

给定一棵树 $^{\dagger}$。在一次 zelda 操作中，你可以进行如下操作：

• 选择树上的两个顶点 $u$ 和 $v$；
• 将从 $u$ 到 $v$ 的路径上的所有顶点压缩成一个顶点。换句话说，从 $u$ 到 $v$ 路径上的所有顶点都会从树中被删除，创建一个新的顶点 $w$。然后，所有原本与该路径上某个顶点有边相连的顶点 $s$，都会与新顶点 $w$ 相连。

上图展示了对顶点 $1$ 和 $5$ 执行一次 zelda 操作的示意图。请你判断，为了使树中只剩下一个顶点，最少需要执行多少次 zelda 操作。

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

输入格式

每个测试点包含多组测试数据。第一行包含一个整数 $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$。

输出格式

对于每组测试数据，输出一个整数，表示使树中只剩下一个顶点所需的最少 zelda 操作次数。

说明/提示

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

在第二个测试用例中，可以按如下方式执行 zelda 操作：

1. $u = 2, v = 1$。新生成的顶点记为 $w = 10$；
2. $u = 4, v = 9$。新生成的顶点记为 $w = 11$；
3. $u = 8, v = 10$。执行完该操作后，树中只剩下一个顶点。

由 ChatGPT 4.1 翻译

样例

4
4
1 2
1 3
3 4
9
3 1
3 5
3 2
5 6
6 7
7 8
7 9
6 4
7
1 2
1 3
2 4
4 5
3 6
2 7
6
1 2
1 3
1 4
4 5
2 6

1
3
2
2