CF1627C.Not Assigning

You are given a tree of $n$ vertices numbered from $1$ to $n$, with edges numbered from $1$ to $n-1$. A tree is a connected undirected graph without cycles. You have to assign integer weights to each edge of the tree, such that the resultant graph is a prime tree.

A prime tree is a tree where the weight of every path consisting of one or two edges is prime. A path should not visit any vertex twice. The weight of a path is the sum of edge weights on that path.

Consider the graph below. It is a prime tree as the weight of every path of two or less edges is prime. For example, the following path of two edges: $2 \to 1 \to 3$ has a weight of $11 + 2 = 13$, which is prime. Similarly, the path of one edge: $4 \to 3$ has a weight of $5$, which is also prime.

Print any valid assignment of weights such that the resultant tree is a prime tree. If there is no such assignment, then print $-1$. It can be proven that if a valid assignment exists, one exists with weights between $1$ and $10^5$ as well.

给你一棵包含 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$，边编号为 $1$ 到 $n-1$。树是一种无环的连通无向图。你需要为树的每条边分配一个整数权重，使得所得图是一棵素数树（prime tree）。

素数树是指：其中任意一条由至多两条边构成的路径的权重均为素数。路径中不允许重复访问任一顶点。路径的权重定义为该路径上所有边的权重之和。

考虑下图所示的图。它是一棵素数树，因为其中所有长度不超过两条边的路径的权重均为素数。例如，由两条边组成的路径 $2 \to 1 \to 3$ 的权重为 $11 + 2 = 13$，是素数；又如，由一条边组成的路径 $4 \to 3$ 的权重为 $5$，也是素数。

请输出任意一组满足条件的边权分配方案，使得所得树为素数树。若不存在这样的方案，则输出 $-1$。可以证明：若存在合法方案，则必存在一组所有边权均在 $1$ 到 $10^5$ 范围内的合法方案。

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer $n$ ($2 \leq n \leq 10^5$) — the number of vertices in the tree.

Then, $n-1$ lines follow. The $i$-th line contains two integers $u$ and $v$ ($1 \leq u, v \leq n$) denoting that edge number $i$ is between vertices $u$ and $v$. It is guaranteed that the edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $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$。

For each test case, if a valid assignment exists, then print a single line containing $n-1$ integers $a_1, a_2, \dots, a_{n-1}$ ($1 \leq a_i \le 10^5$), where $a_i$ denotes the weight assigned to the edge numbered $i$. Otherwise, print $-1$.

If there are multiple solutions, you may print any.

对于每个测试用例，如果存在合法的赋值方案，则输出一行包含 $n-1$ 个整数 $a_1, a_2, \dots, a_{n-1}$（$1 \leq a_i \le 10^5$），其中 $a_i$ 表示分配给编号为 $i$ 的边的权重；否则，输出 $-1$。

如果存在多个解，你可以输出任意一个。

For the first test case, there are only two paths having one edge each: $1 \to 2$ and $2 \to 1$, both having a weight of $17$, which is prime.

The second test case is described in the statement.

It can be proven that no such assignment exists for the third test case.

对于第一个测试用例，仅有两条各含一条边的路径：$1 \to 2$ 和 $2 \to 1$，它们的权重均为 $17$，而 $17$ 是质数。

第二个测试用例已在题目描述中给出。

可以证明：第三个测试用例不存在满足条件的赋值方案。