Copil Copac 被给予一个 $$$n-1$$$ 边的列表,描述 $$$n$$$ 顶点的树。他决定使用以下算法来绘制它:
- 步骤$$$0$$$:绘制第一个顶点(顶点$$$1$$$)。转到步骤$$$1$$$。
- 步骤$$$1$$$:对于输入中的每条边,按顺序:如果边将已绘制的顶点$$$u$$$连接到未绘制的顶点$$$v$$$,则他将绘制未绘制的顶点$$$v$$$和边。检查完每条边后,转到步骤 $$$2$$$。
- 步骤$$$2$$$:如果绘制了所有顶点,则终止算法。否则,转到步骤$$$1$$$。
读数次数定义为 Copil Copac 执行步骤 $$$1$$$ 的次数。
求 Copil Copac 绘制树所需的读数数量。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$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$$$) - 表明 $$$(u_i,v_i)$$$ 是列表中的第 $$$i$$$ 条边。保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 Copil Copac 绘制树所需的读数数量。
示例
输入 #1
2 6 4 5 1 3 1 2 3 4 1 6 7 5 6 2 4 2 7 1 3 1 2 4 5
输出 #1
2 3
注意
在第一个测试用例中:
第一次读取后,树将如下所示:
第二次读取后:
因此,Copil Copac 需要 $$$2$$$ 读数来绘制树。