Interactive Transitions

The Innopolis campus consists of $n$ buildings connected by $m$ transitions. Each transition connects two distinct buildings, and no two buildings are connected by more than one transition.

It is known that each building has a light that can be turned on or off. Initially, the lights of all buildings are off. The campus dispatcher can turn the light of any building on or off in a single action. The dispatcher can also press the "turn on" button if the light is already on, or press the "turn off" button if it is already off. These actions do not change the state of the building's light.

Similarly, each transition has a light that can be turned on or off. Initially, the lights of all transitions are off. However, unlike the building lights, the transition lights change automatically: if, after an action by the dispatcher, the state of the lights of the two buildings connected by a transition is the same, the transition light also switches to that state; otherwise, it remains unchanged.

In other words, if after an action by the dispatcher the lights of both buildings connected by a transition are off, the transition light also turns off. If the lights of both buildings connected by a transition are on, the transition light also turns on. If the light of one building is on and the other is off, the state of the transition light does not change.

Before the arrival of the informatics olympiad participants, the campus director determined whether each building and each transition should be lit.

Check whether the dispatcher can fulfill the director's request by performing an arbitrary number of actions. If it is possible, find any such sequence of actions. Solutions that correctly determine the possibility of achieving the desired lighting state, but do not provide the required sequence of actions, will receive partial points.

Input

Each test contains one or more test cases. The first line of the test contains an integer $t$ — the number of test cases ($1 \le t \le 50\,000$). The descriptions of the test cases follow. Each test case is described as follows:

The first line contains integers $n$ — the number of buildings, and $m$ — the number of transitions ($1 \le n \le 10^5$, $0 \le m \le 2 \cdot 10^5$).

The next $m$ lines contain the descriptions of the transitions.

The $i$-th line contains integers $a_i, b_i, c_i$ — the indices of the buildings connected by the $i$-th transition, and the required lighting state of the $i$-th transition, respectively ($1 \le a_i, b_i \le n$, $a_i \neq b_i$, $0 \le c_i \le 1$). If $c_i = 0$, the $i$-th transition light must be off, and if $c_i = 1$, it must be on.

The last line contains $n$ integers $d_1, d_2, \dots, d_n$ — the required lighting state of the buildings ($0 \le d_i \le 1$). If $d_v = 0$, the light of building $v$ must be off, and if $d_v = 1$, it must be on.

The sum of $n$ over all test cases does not exceed $10^5$. The sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case:

• If there is no sequence of actions that results in the required lighting state of the buildings and transitions, output "NO".
• If a sequence of actions exists, output "YES". If you do not want to provide the sequence of actions itself, output the number 1 on the next line and proceed to the next test case. If you want to provide the sequence of actions, output an integer $s$ on the next line — the number of actions ($0 \le s \le 10^6$, the sum of $s$ over all test cases must not exceed $10^6$), and in the next $s$ lines, output the actions themselves.

In the $i$-th line ($1 \le i \le s$), output two integers: $v_i$ — the index of the building where the lighting state is changed, and $x_i$ — the new lighting state ($1 \le v_i \le n$, $0 \le x_i \le 1$; if $x_i = 0$, the light of building $v_i$ is turned off, if $x_i = 1$, the light of building $v_i$ is turned on).

Examples

Input 1

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

Output 1

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

Note

The example contains five test cases.

In the first case, there are 4 buildings, represented by circles, and 4 transitions, represented by lines. The presence of a building or transition light is indicated by a bold line. The desired lighting can be achieved in 5 actions. The figures below show the initial lighting state and the state after each action.

In the second case, it is required to obtain the following configuration of 4 buildings and 4 transitions, but it is impossible to do so.

In the third case, there is one building where the light needs to be turned on. This can be done in one action.

In the fourth case, there is one building where the light must be off. A possible sequence of actions is the single action of turning off the light in the building. This is a correct action, even though the light was already off.

In the fifth case, there are two buildings and one transition, and all lights must be off. An empty sequence of actions is a correct sequence leading to such a configuration.