Background

Translated from ROI 2024 D2T2.

The ROI venue, Innopolis University, consists of $n$ buildings and $m$ corridors. Each corridor connects two different buildings, and there is at most one corridor between any two buildings.

It is known that each building has a light that can be turned on or off. Initially, the lights in all buildings are off. In one operation, the campus administrator can turn on or turn off the light in any building. The administrator may also press the “turn on” button when the light is already on, or press the “turn off” button when the light is already off. Such operations do not change the building’s light state.

Similarly, each corridor also has a light that can be turned on or off. Initially, all corridor lights are also off. However, unlike building lights, corridor lights change automatically: after the administrator’s operation, if the two buildings connected by that corridor have the same light state, then the corridor light will also become that same state; otherwise, it does not change.

In other words, after the administrator’s operation, if both endpoint building lights are off, then the corridor light will be turned off as well. If both endpoint building lights are on, then the corridor light will be turned on as well. If one endpoint building light is on and the other is off, then the corridor light state remains unchanged.

Problem Description

Before ROI starts, the campus director decides whether each building and each corridor should be lit. You need to check whether the administrator can achieve the director’s requirement using any number of operations. If it is possible, find any sequence of operations that satisfies the requirement. A solution that correctly determines whether the desired light configuration is achievable, even without providing an operation sequence, can still get half of the score for that test.

Input Format

The input contains multiple test cases. The first line contains an integer $t$, the number of test cases ($1 \leq t \leq 50000$).

For each test case:

The first line contains two integers $n$ and $m$, the number of buildings and the number of corridors ($1 \leq n \leq 10^5$, $0 \leq m \leq 2 \times 10^5$).

The next $m$ lines describe the corridors. The $i$-th line contains three integers $a_i$, $b_i$, $c_i$: the indices of the two buildings connected by the $i$-th corridor, and the required final light state of the $i$-th corridor ($1 \leq a_i, b_i \leq n$, $a_i \ne b_i$, $0 \leq c_i \leq 1$). If $c_i = 0$, then the final corridor light state should be off; if $c_i = 1$, it should be on.

The last line contains $n$ integers $d_1, d_2, \dots, d_n$, the required final light states of the buildings ($0 \leq d_i \leq 1$). If $d_v = 0$, then the final light state of building $v$ should be off; if $d_v = 1$, it should be on.

The sum of all $n$ over the test cases does not exceed $10^5$, and the sum of all $m$ does not exceed $2 \times 10^5$.

Output Format

For each test case:

• If there is no sequence of operations that makes the light states of all buildings and corridors match the requirements, output NO.
• Otherwise, output YES. If you do not show the actual operation sequence (and only get partial points), output $-1$ on the next line and then proceed to the next test case (if any). If you do show an operation sequence, output an integer $s$ on the next line, the number of operations ($0 \leq s \leq 10^6$, and the sum of all $s$ over the test cases does not exceed $10^6$). Then, in the next $s$ lines, output the operations in the following format:
  • On the $i$-th line ($1 \leq i \leq s$), output two integers $v_i, x_i$: the index of the building whose light state is being set, and the new light state ($1 \leq v_i \leq n$, $0 \leq x_i \leq 1$). If $x_i = 0$, it means turning off the light in building $v_i$; if $x_i = 1$, it means turning on the light in building $v_i$.

5
4 4
1 2 0
2 3 1
3 4 0
2 4 1
0 1 0 0
4 4
1 2 0
2 3 1
3 4 0
4 1 1
0 1 0 1
1 0
1
1 0
0
2 1
1 2 0
0 0

YES
5
4 1
3 1
2 1
3 0
4 0
NO
YES
1
1 1
YES
1
1 0
YES
0

Hint

Explanation of the samples:

The first test case contains $4$ buildings (shown as circles) and $4$ corridors (shown as lines). The light states of buildings and corridors are indicated by bold lines (if bold, it means the light is on). To reach the required light configuration, $5$ operations are needed. The figure below shows the initial light states and the states after each operation:

In the second test case, we need to reach the following configuration of buildings and corridors, but it is impossible:

In the third test case, one building needs to have its light turned on. This can be done in one operation.

In the fourth test case, one building needs to have its light turned off. A feasible operation sequence is one operation that turns off the light in that building. Even though the light is already off, such an operation is still valid.

In the fifth test case, there are two buildings and one corridor, and all lights need to be off. An empty operation sequence is also a feasible solution.

Constraints are given in the input format.

Translated by ChatGPT 5