CF1615D X(or)-mas Tree

圣诞夜前夕，Santa 正在疯狂地布置他的新圣诞树！这棵树有 $n$ 个节点，通过 $n-1$ 条边连接。每条树边上都挂着一串圣诞灯，这串灯可以用一个二进制整数表示。 有 $m$ 个小精灵前来欣赏圣诞树。每个小精灵被分配了两个节点 $a$ 和 $b$，他会观察从 $a$ 到 $b$ 的简单路径上的所有灯。之后，这个小精灵最喜欢的数字就是该路径上所有边上灯的值的按位异或（bitwise XOR）。 然而，北极最近刚刚从一场严重的流感中恢复过来。由于这个原因，Santa 忘记了他在树上一些边上挂的灯的配置，而且他已经离开了北极！幸运的是，小精灵们帮了忙，每个人都告诉了 Santa 他被分配的节点对 $(a_i, b_i)$，以及他最喜欢的数字中二进制表示下 $1$ 的个数的奇偶性。换句话说，他记得他最喜欢的数字的二进制表示中 $1$ 的数量是奇数还是偶数。 请你帮助 Santa 判断这些记忆是否可能一致。如果可能，请还原出树上每条边的灯的配置，也许你会因此名垂青史！

第一行包含一个整数 $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 < 2^{30}$），表示节点 $x$ 和 $y$ 之间有一条边。如果 - $v = -1$：Santa 不记得这条边上的灯的配置。 - $v \geq 0$：这条边上的灯的配置为 $v$。 接下来的 $m$ 行，每行包含三个整数 $a$、$b$ 和 $p$（$1 \leq a, b \leq n$；$a \neq b$；$0 \leq p \leq 1$），表示小精灵被分配的两个节点，以及他最喜欢的数字中 $1$ 的个数的奇偶性。 保证所有测试用例中 $n$ 的总和和 $m$ 的总和都不超过 $2 \cdot 10^5$。 保证给定的边构成一棵树。

对于每个测试用例，首先输出一行 YES 或 NO（大小写均可），表示是否存在与 Santa 的记忆一致的树。 如果答案是 YES，接下来输出 $n-1$ 行，每行包含三个整数 $x$、$y$ 和 $v$（$1 \leq x, y \leq n$；$0 \leq v < 2^{30}$），表示边及其上的整数。边的集合必须与输入中相同，如果某条边的值在输入中已给定，则不能更改。你可以按任意顺序输出这些边。 如果有多组答案，输出任意一组均可。

第一个测试用例对应题面中的图片。 一种可行的方案是将边 $(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$ 的个数为奇数）。 注意，还有其他可行的答案。 由 ChatGPT 4.1 翻译