在一个古老王国的中心,生长着传说中的生命之树——唯一一棵生命之树,也是整个世界魔法力量的源泉。该树由 $$$n$$$ 个节点组成。这棵树的每个节点都是一个神奇的源,通过神奇的通道(边缘)连接到其他此类源。树中总共有 $$$n-1$$$ 个通道,第 $$$i$$$ 个通道连接节点 $$$v_i$$$ 和 $$$u_i$$$。此外,树中任意两个节点之间的通道都存在唯一的简单路径。
然而,流经这些通道的魔力必须是平衡的;否则,生命之树的力量可能会扰乱自然秩序,造成灾难性的后果。王国的先贤们发现,当两条魔法通道汇聚到一个节点时,它们之间就会产生危险的“魔法共振”。为了保护生命之树并维持其平衡,有必要选择几条路径并沿着它们执行特殊的仪式。路径是一系列不同的节点 $$$v_1, v_2, \ldots, v_k$$$,其中每对相邻节点 $$$v_i$$$ 和 $$$v_{i+1}$$$ 通过通道连接。当圣人们沿着这样的路径进行仪式时,通道 $$$(v_i, v_{i+1})$$$ 和 $$$(v_{i+1}, v_{i+2})$$$ 之间的共振振动在每个 $$$1 \leq i \leq k - 2$$$ 中被阻止。
圣人的任务是选择最少数量的路径并沿着它们执行仪式以阻止所有共振。这意味着对于从单个节点发出的每一对通道,必须存在至少一个包含这两个通道的选定路径。
帮助圣人们找到最少数量的此类路径,以便保持生命之树的神奇平衡,并使其力量继续滋养整个世界!
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 4 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 5 \cdot 10^5$$$) — 生命之树中的节点数。
每个测试用例的以下 $$$n - 1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$v_i$$$ 和 $$$u_i$$$ ($$$1 \leq v_i < u_i \leq n$$$) — 连接节点 $$$v_i$$$ 和 $$$u_i$$$ 的通道。
保证任意两个节点之间存在通过通道的唯一简单路径。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——圣贤们为防止灾难而需要选择的最小路径数。
示例
输入 #1
5 4 1 2 2 3 3 4 2 1 2 4 1 2 1 3 1 4 8 3 7 2 4 1 2 2 5 3 6 1 3 3 8 6 2 3 1 2 3 6 1 5 1 4
输出 #1
1 0 3 7 3
注意
在第一个测试用例中,有两对通道从单个节点发出:$$$(1, 2)$$$ 和 $$$(2, 3)$$$、$$$(2, 3)$$$ 和 $$$(3, 4)$$$。沿着$$$1-2-3-4$$$路径进行仪式就足够了。因此,答案是$$$1$$$。
在第二个测试用例中,没有从单个节点发出的通道对,因此答案是 $$$0$$$。
在第三个测试用例中,可以沿着路径 $$$2-1-3$$$、$$$2-1-4$$$ 和 $$$3-1-4$$$ 执行仪式。