← 返回题目列表

Codeforces · 2040/D

D. 非素数树

中文机器翻译题面 查看原题

给你一棵有 $$$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$$$ 的相应元素。

第一个测试用例中树的图像

第二个测试用例中树的图像