树是一个无环的连通无向图。考虑一棵有 $n$ 个顶点的树，顶点标号为 $1, 2, \dots, n$。如果一条边 $(u, v)$ 满足存在一个整数 $d > 1$，使得 $u$ 的标号和 $v$ 的标号都能被 $d$ 整除，则称该边为“坏边”。例如，在下方的树中，有三条坏边：$(6, 4)$ 均能被 $2$ 整除，$(2, 6)$ 均能被 $2$ 整除，$(3, 6)$ 均能被 $3$ 整除：

你的目标是重新标记树的顶点，使得坏边的数量尽可能少。例如，如果你将上述树的顶点按如下方式重新标记，则只会存在一条坏边 $(3, 6)$：

树中的坏边越少，你获得的分数就越高。

这是一个仅输出答案的问题。PCMS 中提供了 10 个输入文件。你需要在本地运行你的程序，并仅提交每个输入文件对应的答案文件。

输入格式

每个输入文件包含多个测试用例。 输入文件的第一行包含该输入文件中的测试用例数量。 每个测试用例描述的第一行包含一个整数 $n$，即树的顶点数。 接下来的 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示由边连接的两个顶点。 单个文件中的所有树具有相同的顶点数。

输出格式

对于每个测试用例，输出一行，包含 $n$ 个不同的整数，范围从 $1$ 到 $n$，表示分配给顶点 $1, 2, \dots, n$ 的标号。

子任务

对于每个输入文件，设该输入文件中所有测试用例的边总数为 $M$，你的解中坏边的总数为 $X$，且 $R = \frac{X}{M}$。该输入文件的得分计算如下：

• 若 $R > 0.4$，得分为 $0$；
• 若 $0.33 < R \le 0.4$，得分为 $1$；
• 若 $0.26 < R \le 0.33$，得分为 $2$；
• 若 $0.19 < R \le 0.26$，得分为 $3$；
• 若 $0.12 < R \le 0.19$，得分为 $4$；
• 若 $0.05 < R \le 0.12$，得分为 $5$；
• 若 $0.01 < R \le 0.05$，得分为 $6$；
• 若 $0.005 < R \le 0.01$，得分为 $7$；
• 若 $0.001 < R \le 0.005$，得分为 $8$；
• 若 $0 < R \le 0.001$，得分为 $9$；
• 若 $R = 0$，得分为 $10$。

样例

输入 1

2
6
1 3
3 5
3 6
6 4
6 2
6
1 2
1 3
1 4
1 5
1 6

输出 1

2 5 3 1 4 6
5 1 2 3 4 6

说明

第一个测试用例即题目描述中展示的例子。重新标记后存在一条坏边 $(6, 3)$，因为 $6$ 和 $3$ 都能被 $3$ 整除。 在第二个测试用例中，存在的边为 $(5, 1), (5, 2), (5, 3), (5, 4)$ 和 $(5, 6)$。它们都不是坏边。 输入文件中共有 $10$ 条边，答案中有 $1$ 条坏边。因此 $M = 10, X = 1, R = 0.1$。根据评分表，该答案可得 $5$ 分。

测试数据结构如下：

• 输入文件 1 包含三棵 7 个顶点的树，如下图所示（从左至右）：

• 输入文件 2 和 3 分别包含 100 棵 10 个顶点和 30 个顶点的随机树。
• 输入文件 4 到 8 包含各种具有特殊结构的随机生成树（例如多叶树、二叉树等）。不同种类树的分布在所有输入中大致相同。
• 输入文件 9 和 10 分别包含 50,000 个顶点和 100,000 个顶点的随机生成树。

初始时，所有输入文件中所有树的顶点标号均为随机。