给你一棵有 $$$n$$$ 个顶点的树。顶点编号从 $$$1$$$ 到 $$$n$$$。
您需要为每条边分配一个权重。令第 $$$i$$$ 条边的权重为 $$$a_i$$$ ($$$1 \leq i \leq n-1$$$)。每条边的权重应为 $$$0$$$ 和 $$$2^{30}-1$$$(含)之间的整数。
你有$$$q$$$条件。每个条件由三个整数 $$$u$$$、$$$v$$$ 和 $$$x$$$ 组成。这意味着从 $$$u$$$ 到 $$$v$$$ 的最短路径上的所有边的按位异或应该是 $$$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}$$$ 是最小的,则打印其中任意一个。
输入
第一行包含两个整数 $$$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$$$ 到 $$$u$$$ 的最短路径上的所有边按位异或$$$v$$$ 应该是$$$x$$$。
输出
如果不存在满足给定条件的$$$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”、“yes”、“Yes”和“YES”将被识别为肯定响应。
示例
输入 #1
4 4 1 2 2 3 3 4 1 4 3 2 4 2 1 3 1 2 3 1
输出 #1
No
输入 #2
6 2 1 2 2 3 3 4 2 5 5 6 1 4 2 2 6 7
输出 #2
Yes 4 2 4 1 6
输入 #3
6 2 1 2 2 3 3 4 2 5 5 6 1 4 3 1 6 5
输出 #3
Yes 6 1 4 3 0
注意
对于第一个示例,不存在满足给定条件的边权重集。
对于第二个示例,两个给定条件是 $$$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}$$$,所以它不可能是答案。