CF1788F.XOR, Tree, and Queries

You are given a tree of $n$ vertices. The vertices are numbered from $1$ to $n$.

You will need to assign a weight to each edge. Let the weight of the $i$-th edge be $a_i$ ($1 \leq i \leq n-1$). The weight of each edge should be an integer between $0$ and $2^{30}-1$, inclusive.

You are given $q$ conditions. Each condition consists of three integers $u$, $v$, and $x$. This means that the bitwise XOR of all edges on the shortest path from $u$ to $v$ should be $x$.

Find out if there exist $a_1, a_2, \ldots, a_{n-1}$ that satisfy the given conditions. If yes, print a solution such that $a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$ is the smallest. Here, $\oplus$ denotes the bitwise XOR operation.

If there are multiple solutions such that $a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$ is the smallest, print any.

给你一棵包含 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。

你需要为每条边分配一个权值。设第 $i$ 条边的权值为 $a_i$（$1 \leq i \leq n-1$）。每条边的权值必须是介于 $0$ 和 $2^{30}-1$（含）之间的整数。

你将获得 $q$ 个约束条件。每个条件由三个整数 $u$、$v$ 和 $x$ 组成，表示从顶点 $u$ 到顶点 $v$ 的最短路径上所有边的权值的按位异或（bitwise XOR）结果应恰好为 $x$。

请判断是否存在满足所有约束条件的权值序列 $a_1, a_2, \ldots, a_{n-1}$。若存在，请输出一个解，使得 $a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$ 的值最小（其中 $\oplus$ 表示按位异或运算）。

若存在多个使 $a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$ 最小的解，输出任意一个即可。

The first line contains two integers $n$ and $q$ ($2 \le n \le 2.5 \cdot 10^5$, $0 \le q \le 2.5 \cdot 10^5$).

The $i$-th of the following $n-1$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \neq y_i$), meaning that the $i$-th edge connects vertices $x_i$ and $y_i$ in the tree.

It is guaranteed that the given edges form a tree.

The following $q$ lines contain information about conditions.

Each line contains three integers $u$, $v$, $x$ ($1 \le u, v \le n$, $u \neq v$, $0 \le x \le 2^{30}-1$), meaning that the bitwise XOR of all edges on the shortest path from $u$ to $v$ should be $x$.

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 2.5 \cdot 10^5$，$0 \le q \le 2.5 \cdot 10^5$）。

接下来的 $n-1$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，$x_i \neq y_i$），表示第 $i$ 条边连接树中的顶点 $x_i$ 和 $y_i$。

保证所给的边构成一棵树。

接下来的 $q$ 行描述约束条件。

每行包含三个整数 $u$、$v$、$x$（$1 \le u, v \le n$，$u \neq v$，$0 \le x \le 2^{30}-1$），表示从 $u$ 到 $v$ 的最短路径上所有边的权值的按位异或（XOR）结果应为 $x$。

If there do not exist $a_1$, $a_2$, ..., $a_{n-1}$ that satisfy the given conditions, print "No".

Otherwise, print "Yes" in the first line.

Then print $n-1$ integers on the next line, where the $i$-th integer is the weight of the $i$-th edge. If there are multiple solutions that satisfy the given conditions, print a solution such that $a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$ is the smallest.

If there are multiple solutions such that $a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$ is the smallest, print any.

When printing "Yes" or "No", you can print each letter in any case (either upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

如果不存在满足给定条件的 $a_1$, $a_2$, ..., $a_{n-1}$，则输出 "No"。

否则，在第一行输出 "Yes"。

然后在下一行输出 $n-1$ 个整数，其中第 $i$ 个整数为第 $i$ 条边的权重。若存在多个满足给定条件的解，则输出使得 $a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$ 最小的解。

若存在多个使得 $a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$ 最小的解，则任选其一输出。

在输出 "Yes" 或 "No" 时，每个字母可使用任意大小写（大写或小写均可）。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均将被识别为肯定回答。

For the first example, there does not exist a set of edge weights that satisfies the given conditions.

For the second example, the two given conditions are $a_1 \oplus a_2 \oplus a_3=2$ and $a_4 \oplus a_5=7$. There can be multiple solutions, for example, $(a_1, a_2, a_3, a_4, a_5)=(1, 2, 1, 4, 3)$.

For the third example, the two given conditions are $a_1 \oplus a_2 \oplus a_3=3$ and $a_1 \oplus a_4 \oplus a_5=5$. There are multiple solutions that satisfy the given conditions.

$(a_1, a_2, a_3, a_4, a_5)=(1, 1, 3, 4, 0)$ satisfies the given conditions, but the bitwise XOR of all edge weights is $7$, which does not have the smallest $a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$, so it cannot be the answer.

对于第一个样例，不存在满足给定条件的边权集合。

对于第二个样例，给出的两个条件是 $a_1 \oplus a_2 \oplus a_3=2$ 和 $a_4 \oplus a_5=7$。存在多种解，例如 $(a_1, a_2, a_3, a_4, a_5)=(1, 2, 1, 4, 3)$。

对于第三个样例，给出的两个条件是 $a_1 \oplus a_2 \oplus a_3=3$ 和 $a_1 \oplus a_4 \oplus a_5=5$。存在多个满足给定条件的解。

$(a_1, a_2, a_3, a_4, a_5)=(1, 1, 3, 4, 0)$ 满足给定条件，但所有边权的按位异或值为 $7$，该值并非最小的 $a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$，因此不能作为答案。