你有一棵树$$$^{\dagger}$$$。在一项塞尔达操作中,您可以执行以下操作:
- 选择树 $$$u$$$ 和 $$$v$$$ 的两个顶点;
- 将 $$$u$$$ 到 $$$v$$$ 路径上的所有顶点压缩为一个顶点。换句话说,从$$$u$$$到$$$v$$$路径上的所有顶点都将从树中删除,并创建一个新的顶点$$$w$$$。然后,从 $$$u$$$ 到 $$$v$$$ 的路径上与某个顶点有边的每个顶点 $$$s$$$ 都将有与顶点 $$$w$$$ 的边。
对顶点 $$$1$$$ 和 $$$5$$$ 执行的 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$$$。
输出
对于每个测试用例,输出一个整数——树只有一个顶点所需的最小塞尔达操作数。
示例
输入 #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
1 3 2 2
注意
在第一个测试用例中,对顶点 $$$2$$$ 和 $$$4$$$ 执行一次塞尔达操作就足够了。
在第二个测试用例中,我们可以执行以下 zelda 操作:
1. $$$u = 2,v = 1$$$。将添加的顶点标记为 $$$w = 10$$$;
2. $$$u = 4,v = 9$$$。将添加的顶点标记为 $$$w = 11$$$;
3. $$$u = 8,v = 10$$$。执行此操作后,树将由单个顶点组成。