Stardew Valley
Contest: Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)
Difficulty rating: 2500
Tags: constructive algorithms, dfs and similar, graphs, trees

Pelican Town represents $$$n$$$ houses connected by $$$m$$$ bidirectional roads. Some roads have NPCs standing on them. Farmer Buba needs to walk on each road with an NPC and talk to them.

Help the farmer find a route satisfying the following properties:

- The route starts at some house, follows the roads, and ends at the same house.
- The route does not follow any road more than once (in both directions together).
- The route follows each road with an NPC exactly once.

It is guaranteed that you can reach any house from any other by walking on the roads with NPCs only.

Input format:
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 5 \cdot 10^5, 1 \leq m \leq 5 \cdot 10^5$$$) — the number of houses and roads in Pelican Town respectively.

In each of the next $$$m$$$ lines, three integers $$$u$$$, $$$v$$$, and $$$c$$$ ($$$1 \leq u, v \leq n, c = 0/1$$$) are given — the ends of the road and whether an NPC is on this road. If $$$c = 1$$$, then the road has an NPC. If $$$c = 0$$$, then the road has no NPC.

The graph may contain multiple edges and loops, and if there are multiple edges with NPCs standing on them, the route must follow each of these roads.

It is guaranteed that you can reach any house from any other by walking on the roads with NPCs only.

It is guaranteed that the sum of $$$n$$$ and $$$m$$$ for all test cases does not exceed $$$5 \cdot 10^5$$$.

Output format:
For each test case, if there is no solution, then output "No" (without quotes).

Otherwise, output "Yes" (without quotes), and then output $$$k$$$ — the number of roads in the route. In the next line, output $$$k + 1$$$ numbers — the houses of the route in the order of traversal. Note that the first house should match the last one, as the route is cyclic.

If there are multiple answers, you can print any of them.

You can output each letter in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Note that in the third test case, there are multiple edges $$$(5, 2)$$$. You must walk on two of them.

Example input:
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

Example output:
NO
YES
3
1 2 3 1 
YES
7
1 2 5 4 3 2 5 1

Editorial:
The edges with $$$0$$$ on them will be called black, the other edges will be called white.
To find such a route, we need the graph to be Eulerian (degree of each vertex is even). To achieve this, we can remove some black edges.
Let's calculate the degree of each vertex (further we will keep this degree in mind) and leave only black edges. Solve the problem independently for each component. If a component has an odd number of vertices with odd degree, we cannot remove edges so that all degrees become even (since removing an edge does not change the parity of the sum of degrees), so in this case the answer is NO. Otherwise, such a route exists. Leave only the spanning tree and run dfs on it. If we leave a vertex and it has an odd degree, we remove an edge to its ancestor. This will work since the sum of the degrees in the component is even.
Finally, we need to find the Eulerian cycle in the resulting graph and print it.