每个测试时间限制：5 秒
每个测试内存限制：512 兆字节

题目描述

有一棵苹果树，有 $n$ 个节点，初始时每个节点上都有一个苹果。你有一张纸，初始时上面没有写任何东西。

你在苹果树上进行遍历，只要树上至少还有一个苹果，就重复执行以下操作：

1. 选择一条苹果路径 $(u, v)$。一条路径 $(u, v)$ 被称为苹果路径，当且仅当该路径上的每一个节点都还有苹果。
2. 设 $d$ 为该路径上的苹果数量（即路径长度，按节点数计），将三个数 $(d, u, v)$ 按此顺序写在纸上。
3. 然后移除该路径 $(u, v)$ 上所有节点的苹果。

这里，路径 $(u, v)$ 指的是从 $u$ 到 $v$ 的唯一最短顶点序列。

设纸上写下的数字序列为 $a$。你的任务是找到字典序最大的可能序列 $a$。

输入格式

每个测试包含多个测试用例。
第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。
接下来每个测试用例的格式如下：

• 第一行包含一个整数 $n$（$1 \leq n \leq 1.5 \times 10^5$）。
• 接下来的 $n-1$ 行，每行包含两个整数 $u, v$（$1 \leq u, v \leq n$），表示树中的一条边。保证输入构成一棵树。

数据保证所有测试用例的 $n$ 之和不超过 $1.5 \times 10^5$。

输出格式

对于每个测试用例，输出字典序最大的可能序列 $a_1, a_2, \dots, a_{|a|}$。可以证明 $|a| \leq 3 \cdot n$。

示例

输入

6
4
1 2
1 3
1 4
4
2 1
2 4
2 3
5
1 2
2 3
3 4
4 5
1
8
6 3
3 5
5 4
4 2
5 1
1 8
3 7
6
3 2
2 6
2 5
5 4
4 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 

样例解释

第一个测试用例，我们按以下步骤操作：

1. 选择苹果路径 $(4,3)$。该路径包含节点 $4,1,3$，每个节点都有苹果（因此是合法苹果路径）。$d = 3$（路径上有 $3$ 个苹果）。按顺序向序列 $a$ 追加 $3,4,3$。然后移除这 $3$ 个节点的苹果。
2. 只剩下节点 $2$ 有苹果。选择苹果路径 $(2,2)$。该路径只包含节点 $2$。$d = 1$（路径上有 $1$ 个苹果）。向序列 $a$ 追加 $1,2,2$，并移除节点 $2$ 的苹果。

最终序列为 $[3,4,3,1,2,2]$。可以证明这是字典序最大的可能序列。