CF1615D.X(or)-mas Tree

'Twas the night before Christmas, and Santa's frantically setting up his new Christmas tree! There are $n$ nodes in the tree, connected by $n-1$ edges. On each edge of the tree, there's a set of Christmas lights, which can be represented by an integer in binary representation.

He has $m$ elves come over and admire his tree. Each elf is assigned two nodes, $a$ and $b$, and that elf looks at all lights on the simple path between the two nodes. After this, the elf's favorite number becomes the bitwise XOR of the values of the lights on the edges in that path.

However, the North Pole has been recovering from a nasty bout of flu. Because of this, Santa forgot some of the configurations of lights he had put on the tree, and he has already left the North Pole! Fortunately, the elves came to the rescue, and each one told Santa what pair of nodes he was assigned $(a_i, b_i)$, as well as the parity of the number of set bits in his favorite number. In other words, he remembers whether the number of $1$'s when his favorite number is written in binary is odd or even.

Help Santa determine if it's possible that the memories are consistent, and if it is, remember what his tree looked like, and maybe you'll go down in history!

圣诞节前夜，圣诞老人正手忙脚乱地布置他的新圣诞树！这棵树共有 $n$ 个节点，由 $n-1$ 条边连接。每条边上都有一串圣诞彩灯，其状态可用一个二进制表示的整数来刻画。

他邀请了 $m$ 位精灵前来欣赏这棵圣诞树。每位精灵被分配两个节点 $a$ 和 $b$，该精灵会观察连接这两个节点的简单路径上所有边上的彩灯。随后，这位精灵的“最爱数字”即为该路径上所有边对应彩灯值的**按位异或（XOR）**结果。

然而，北极地区刚刚经历了一场严重的流感疫情。受此影响，圣诞老人忘记了部分彩灯的配置，且已离开北极！幸运的是，精灵们挺身而出，每位精灵都向圣诞老人报告了自己被分配的节点对 $(a_i, b_i)$，以及其“最爱数字”的二进制表示中 1 的个数的奇偶性。换言之，他仅记得该最爱数字的二进制形式中含奇数个 $1$ 还是偶数个 $1$。

请帮助圣诞老人判断：这些精灵的记忆是否可能一致；若可能，请还原出圣诞树上各条边的彩灯配置（即各边对应的整数值）。说不定，你将因此名垂青史！

The first line contains one integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. Then $t$ cases follow.

The first line of each test case contains two integers, $n$ and $m$ ($2 \leq n \leq 2 \cdot 10^5$; $1 \leq m \leq 2 \cdot 10^5$) — the size of tree and the number of elves respectively.

The next $n-1$ lines of each test case each contains three integers, $x$, $y$, and $v$ ($1 \leq x, y \leq n$; $-1 \leq v \lt 2^{30}$) — meaning that there's an edge between nodes $x$ and $y$. If

• $v = -1$: Santa doesn't remember what the set of lights were on for this edge.
• $v \geq 0$: The set of lights on the edge is $v$.

The next $m$ lines of each test case each contains three integers, $a$, $b$, and $p$ ($1 \leq a, b \leq n$; $a \neq b$; $0 \leq p \leq 1$) — the nodes that the elf was assigned to, and the parity of the number of set bits in the elf's favorite number.

It is guaranteed that the sum of all $n$ and the sum of all $m$ don't exceed $2 \cdot 10^5$ each.

It is guaranteed that the given edges form a tree.

第一行包含一个整数 $t$（$1 \leq t \leq 2 \cdot 10^4$）—— 表示测试用例的数量。随后是 $t$ 组测试用例。

每组测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 2 \cdot 10^5$；$1 \leq m \leq 2 \cdot 10^5$）—— 分别表示树的大小和精灵的数量。

每组测试用例的接下来 $n-1$ 行，每行包含三个整数 $x$、$y$ 和 $v$（$1 \leq x, y \leq n$；$-1 \leq v \lt 2^{30}$）—— 表示节点 $x$ 与节点 $y$ 之间存在一条边。其中：

• 若 $v = -1$：圣诞老人不记得该边上点亮的灯的集合；
• 若 $v \geq 0$：该边上点亮的灯的集合为 $v$。

每组测试用例的接下来 $m$ 行，每行包含三个整数 $a$、$b$ 和 $p$（$1 \leq a, b \leq n$；$a \neq b$；$0 \leq p \leq 1$）—— 表示该精灵被分配到的两个节点，以及该精灵最喜爱数字的二进制表示中“1”的个数的奇偶性（$p=0$ 表示偶数个，$p=1$ 表示奇数个）。

保证所有测试用例的 $n$ 之和与所有测试用例的 $m$ 之和各自均不超过 $2 \cdot 10^5$。

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

For each test case, first print either YES or NO (in any case), whether there's a tree consistent with Santa's memory or not.

If the answer is YES, print $n-1$ lines each containing three integers: $x$, $y$, and $v$ ($1 \le x, y \le n$; $0 \le v \lt 2^{30}$) — the edge and the integer on that edge. The set of edges must be the same as in the input, and if the value of some edge was specified earlier, it can not change. You can print the edges in any order.

If there are multiple answers, print any.

对于每个测试用例，首先输出 YES 或 NO（字母大小写任意），表示是否存在一棵与圣诞老人记忆一致的树。

如果答案为 YES，则输出 $n-1$ 行，每行包含三个整数：$x$、$y$ 和 $v$（其中 $1 \le x, y \le n$；$0 \le v \lt 2^{30}$），分别表示一条边及其上的整数值。所输出的边集必须与输入中的边集完全相同；若某条边的值在输入中已被指定，则该值不得更改。边的输出顺序可以任意。

若存在多个合法解，输出任意一个即可。

The first test case is the image in the statement.

One possible answer is assigning the value of the edge $(1, 2)$ to $5$, and the value of the edge $(2, 5)$ to $3$. This is correct because:

• The first elf goes from node $2$ to node $3$. This elf's favorite number is $4$, so he remembers the value $1$ (as $4$ has an odd number of $1$ bits in its binary representation).
• The second elf goes from node $2$ to node $5$. This elf's favorite number is $3$, so he remembers the value $0$ (as $3$ has an even number of $1$ bits in its binary representation).
• The third elf goes from node $5$ to node $6$. This elf's favorite number is $7$, so he remembers the value $1$ (as $7$ has an odd number of $1$ bits in its binary representation).
• The fourth elf goes from node $6$ to node $1$. This elf's favorite number is $1$, so he remembers the value $1$ (as $1$ has an odd number of $1$ bits in its binary representation).
• The fifth elf goes from node $4$ to node $5$. This elf's favorite number is $4$, so he remembers the number $1$ (as $4$ has an odd number of $1$ bits in its binary representation).

Note that there are other possible answers.

第一个测试用例即为题目描述中的图片。

一种可能的解答是：将边 $(1, 2)$ 的权值赋为 $5$，边 $(2, 5)$ 的权值赋为 $3$。该解答是正确的，原因如下：

• 第一只精灵从节点 $2$ 走到节点 $3$。这只精灵最喜爱的数字是 $4$，因此它记住的值为 $1$（因为 $4$ 的二进制表示中包含奇数个 $1$ 位）。
• 第二只精灵从节点 $2$ 走到节点 $5$。这只精灵最喜爱的数字是 $3$，因此它记住的值为 $0$（因为 $3$ 的二进制表示中包含偶数个 $1$ 位）。
• 第三只精灵从节点 $5$ 走到节点 $6$。这只精灵最喜爱的数字是 $7$，因此它记住的值为 $1$（因为 $7$ 的二进制表示中包含奇数个 $1$ 位）。
• 第四只精灵从节点 $6$ 走到节点 $1$。这只精灵最喜爱的数字是 $1$，因此它记住的值为 $1$（因为 $1$ 的二进制表示中包含奇数个 $1$ 位）。
• 第五只精灵从节点 $4$ 走到节点 $5$。这只精灵最喜爱的数字是 $4$，因此它记住的值为 $1$（因为 $4$ 的二进制表示中包含奇数个 $1$ 位）。

注意：本题存在其他可能的正确答案。