该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

一叶孤舟浮碧水，几行轻雁过遥天

题目描述

给定一棵树。在一次 zelda 操作中，你可以进行如下操作：

1.选择树上的两个顶点 $u$ 和 $v$；

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

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

一棵树是一个连通且无环的无向图。

（术语说明：树是一种特殊的图，它由 $n$ 个顶点和 $n-1$ 条边组成，任意两个顶点之间有且仅有一条路径相连。）

输入格式

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

样例输入

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

数据范围

• $1 \le t \le 10^4$
• $2 \le n \le 10^5$
• 所有测试数据中 $n$ 的总和不超过 $10^5$

题目来源：codeforces