← 返回题目列表

Codeforces · 1994/F

F. 星露谷物语

中文机器翻译题面 查看原题

鹈鹕镇代表由 $$$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)$$$。你必须在其中两个上行走。