一棵苹果树有 $$$n$$$ 个节点,最初每个节点都有一个苹果。你手里有一张纸,最初上面什么也没写。
你正在苹果树上遍历,只要还剩下至少一个苹果,就执行以下操作:
- 选择一个 苹果路径 $$$(u,v)$$$。路径 $$$(u,v)$$$ 称为 苹果路径 当且仅当路径 $$$(u,v)$$$ 上的每个节点上都有一个苹果。
- 设 $$$d$$$ 为路径上苹果的数量,在纸上按顺序写下三个数字 $$$(d,u,v)$$$。
- 然后删除路径$$$(u,v)$$$上的所有苹果。
这里,路径 $$$(u, v)$$$ 指的是从 $$$u$$$ 到 $$$v$$$ 的唯一最短路径上的顶点序列。
设纸上的数字顺序为$$$a$$$。你的任务是找到字典顺序上最大的可能序列$$$a$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个数字 $$$n$$$ ($$$1 \le n \le 1.5 \cdot 10^5$$$)。
每个测试用例的以下 $$$n-1$$$ 行包含两个数字 $$$u,v$$$ ($$$1 \le u,v \le n$$$)。保证输入形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$1.5 \cdot 10^5$$$。
输出
对于每个测试用例,输出字典顺序最大的可能序列 $$$a_1, a_2, \ldots, a_{|a|}$$$。可以证明 $$$|a| \le 3 \cdot n$$$。
示例
输入复制
641 21 31 442 12 42 351 22 33 44 5186 33 55 44 25 11 83 763 22 62 55 44 1
输出复制
3 4 3 1 2 2 3 4 3 1 1 1 5 5 1 1 1 1 5 8 7 2 4 2 1 6 6 5 6 1 1 3 3
注意
在第一个测试用例中,我们执行以下步骤:
- 选择苹果路径 $$$(4, 3)$$$。该路径由节点 $$$4, 1, 3$$$ 组成,每个节点都有一个苹果(因此它是有效的苹果路径)。 $$$d = 3$$$ 因为这条路径上有 $$$3$$$ 苹果。按顺序将 $$$3, 4, 3$$$ 添加到我们的序列 $$$a$$$ 中。现在,从这些 $$$3$$$ 顶点中删除苹果。
- 只有节点 $$$2$$$ 还剩下一个苹果。选择苹果路径 $$$(2, 2)$$$。该路径仅包含单个节点$$$2$$$。 $$$d = 1$$$ 因为这条路径上有 $$$1$$$ 苹果。按顺序将 $$$1, 2, 2$$$ 添加到我们的序列 $$$a$$$ 中,并从 $$$2$$$ 中删除苹果。
最终序列是 $$$[3, 4, 3, 1, 2, 2]$$$。可以证明这是字典顺序上可能的最大序列。