给你一棵有 $$$n$$$ 个顶点的树。
您需要构造一个数组 $$$a_1, a_2, \ldots, a_n$$$,长度为 $$$n$$$,由从 $$$1$$$ 到 $$$2 \cdot n$$$ 的唯一整数组成,并且对于树的每个边 $$$u_i \leftrightarrow v_i$$$,值 $$$|a_{u_i} - a_{v_i}|$$$ 不是素数。
查找任何满足这些条件的数组,或者报告不存在这样的数组。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。
接下来的 $$$n - 1$$$ 行包含树的边,每行一个边。第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$),表示节点 $$$u_i$$$ 和 $$$v_i$$$ 之间的边。
保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10 ^ 5$$$。
输出
对于每个测试用例,如果存在满足条件的数组,则打印其元素 $$$a_1, a_2, \ldots, a_n$$$。否则,打印$$$-1$$$。
示例
输入 #1
2 5 1 2 2 3 2 4 3 5 7 1 2 1 3 2 4 3 5 3 6 3 7
输出 #1
2 10 1 6 5 8 7 12 1 4 6 3
注意
可能的答案如下所示。其中写入的不是顶点编号,而是数组 $$$a$$$ 的相应元素。
第一个测试用例中树的图像
第二个测试用例中树的图像