← 返回题目列表

Codeforces · 1627/C

C. 未分配

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

给你一棵由 $$$n$$$ 顶点组成的树,编号从 $$$1$$$ 到 $$$n$$$,边编号从 $$$1$$$ 到 $$$n-1$$$。树是无环的连通无向图。您必须为树的每个边分配整数权重,以便生成的图是素数树。

素数树是由一条或两条边组成的每条路径的权重为素数的树。路径不应两次访问任何顶点。路径的权重是该路径上边权重的总和。

考虑下图。它是一棵素数树,因为两条或更少边的每条路径的权重都是素数。例如,以下两条边的路径: $$$2 \to 1 \to 3$$$ 的权重为 $$$11 + 2 = 13$$$,它是素数。类似地,一条边的路径:$$$4 \to 3$$$ 的权重为$$$5$$$,它也是素数。

打印任何有效的权重分配,使得生成的树是素数树。如果没有这样的分配,则打印$$$-1$$$。可以证明,如果存在有效的分配,则也存在权重在 $$$1$$$ 和 $$$10^5$$$ 之间的分配。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — 树中的顶点数。

然后是 $$$n-1$$$ 行。第 $$$i$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$) 表示边号 $$$i$$$ 位于顶点 $$$u$$$ 和 $$$v$$$ 之间。保证边形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,如果存在有效分配,则打印一行,其中包含 $$$n-1$$$ 整数 $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$1 \leq a_i \le 10^5$$$),其中 $$$a_i$$$ 表示分配给编号为 $$$i$$$ 的边的权重。否则,打印$$$-1$$$。

如果有多个解决方案,您可以打印任何一个。

示例

输入 #1

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

输出 #1

17
2 5 11
-1

注意

对于第一个测试用例,只有两条路径各有一条边:$$$1 \to 2$$$ 和 $$$2 \to 1$$$,两者的权重均为 $$$17$$$,均为素数。

声明中描述了第二个测试用例。

可以证明第三个测试用例不存在这样的分配。