'那是圣诞节前一天晚上,圣诞老人正在疯狂地布置他的新圣诞树!树中有 $$$n$$$ 个节点,由 $$$n-1$$$ 边连接。在树的每条边上,都有一组圣诞灯,可以用二进制表示的整数来表示。
他让 $$$m$$$ 精灵过来欣赏他的树。每个精灵都被分配了两个节点,$$$a$$$ 和 $$$b$$$,并且该精灵查看两个节点之间的简单路径上的所有灯光。此后,精灵最喜欢的数字将成为该路径边缘上的灯光值的按位异或。
然而,北极已经从一场严重的流感中恢复过来。因此,圣诞老人忘记了他在树上放的一些灯的配置,他已经离开了北极!幸运的是,精灵们前来救援,每个精灵都告诉圣诞老人他被分配了哪一对节点 $$$(a_i, b_i)$$$,以及他最喜欢的数字中设置位数的奇偶性。换句话说,当他最喜欢的数字用二进制写成时,他记得$$$1$$$的数量是奇数还是偶数。
帮助圣诞老人确定记忆是否可能一致,如果是,记住他的树是什么样子,也许你会载入史册!
输入
第一行包含一个整数 $$$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$$$ 和 $$$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$$$) - 精灵被分配到的节点,以及精灵最喜欢的数字中设置位数的奇偶校验。
保证所有 $$$n$$$ 的总和以及所有 $$$m$$$ 的总和各不超过 $$$2 \cdot 10^5$$$。
保证给定的边形成一棵树。
输出
对于每个测试用例,首先打印 YES 或 NO(在任何情况下),无论是否有一棵树与圣诞老人的记忆一致。
如果答案为“是”,则打印 $$$n-1$$$ 行,每行包含三个整数:$$$x$$$、$$$y$$$ 和 $$$v$$$ ($$$1 \le x, y \le n$$$; $$$0 \le v < 2^{30}$$$) — 边和该边上的整数。边的集合必须与输入中的相同,并且如果先前指定了某些边的值,则它不能更改。您可以按任何顺序打印边缘。
如果有多个答案,请打印其中一个。
示例
输入 #1
4 6 5 1 2 -1 1 3 1 4 2 7 6 3 0 2 5 -1 2 3 1 2 5 0 5 6 1 6 1 1 4 5 1 5 3 1 2 -1 1 3 -1 1 4 1 4 5 -1 2 4 0 3 4 1 2 3 1 3 3 1 2 -1 1 3 -1 1 2 0 1 3 1 2 3 0 2 1 1 2 1 1 2 0
输出 #1
YES 1 2 0 1 3 1 2 4 7 3 6 0 2 5 0 YES 1 2 1 1 3 0 1 4 1 4 5 1 NO NO
注意
第一个测试用例是语句中的图像。
一种可能的答案是将边 $$$(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$$$位)。
请注意,还有其他可能的答案。