鹈鹕镇代表由 $$$m$$$ 双向道路连接的 $$$n$$$ 栋房屋。有些道路上有 NPC 站立。农民布巴需要和 NPC 一起走在每条路上并与他们交谈。
帮助农民找到满足以下属性的路线:
- 路线从某个房屋开始,沿着道路行驶,并在同一房屋结束。
- 该路线不会多次沿着任何道路(在两个方向上一起)。
- 该路线沿着每条有 NPC 的道路恰好出现一次。
保证你可以通过走在只有NPC的道路上从任何其他房子到达任何房子。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — 测试用例的数量。然后是测试用例的描述。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 5 \cdot 10^5, 1 \leq m \leq 5 \cdot 10^5$$$)——分别是鹈鹕镇的房屋和道路的数量。
在接下来的 $$$m$$$ 行中,给出了三个整数 $$$u$$$、$$$v$$$ 和 $$$c$$$ ($$$1 \leq u, v \leq n, c = 0/1$$$) — 道路的尽头以及 NPC 是否在这条道路上。如果$$$c = 1$$$,则道路上有 NPC。如果$$$c = 0$$$,则道路上没有 NPC。
该图可能包含多条边和环,如果有多条边上站立着 NPC,则路线必须遵循每条道路。
保证你可以通过走在只有NPC的道路上从任何其他房子到达任何房子。
保证所有测试用例的 $$$n$$$ 和 $$$m$$$ 之和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,如果没有解决方案,则输出“No”(不带引号)。
否则,输出“Yes”(不带引号),然后输出 $$$k$$$ — 路线中的道路数量。在下一行中,输出 $$$k + 1$$$ 个数字——按遍历顺序排列的路线房屋。请注意,第一个房子应该与最后一个房子匹配,因为路线是循环的。
如果有多个答案,您可以打印其中任何一个。
您可以在任何情况下输出每个字母(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。
示例
输入 #1
3 3 2 1 2 1 2 3 1 3 3 1 2 1 1 3 1 2 3 0 5 9 1 2 0 5 2 1 5 4 1 5 1 1 2 3 1 5 2 1 4 1 0 4 3 0 5 2 0
输出 #1
NO YES 3 1 2 3 1 YES 7 1 2 5 4 3 2 5 1
注意
请注意,在第三个测试用例中,有多个边 $$$(5, 2)$$$。你必须在其中两个上行走。