CF1627C Not Assigning

给定一棵有 $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$ 行，每行包含两个整数 $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 \to 2$ 和 $2 \to 1$，权值都是 $17$，是质数。  第二组测试数据如题面所述。 可以证明，第三组测试数据不存在合法的分配方案。 由 ChatGPT 4.1 翻译