Background

"Just twenty billion, just two thousand years, that's not enough."
"The power I possess is even more than you can imagine."

You can't defeat the Righteous Flame.
But to prove your imagination is rich, you need to solve a construction problem.

Problem Description

You have an undirected connected graph with \( n \) vertices and \( m \) edges. Each vertex has an initial value \( a_i \) and a target value \( b_i \). You can perform the following operations on this graph:
- Choose an integer \( c \), which must satisfy \( |c| \le 10^{18} \);
- Select a chain with 3 vertices and 2 edges;
- Subtract \( 2c \) from the value of the middle vertex and add \( c \) to the values of the other two vertices.

Determine if you can perform several operations to make the value of each vertex equal to \( b_i \). If possible, you need to output the plan with the number of operations not exceeding \( 4n \).

Note that \( c \) can be negative.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer \( T \), the number of test cases.
For each test case, the first line contains two positive integers \( n \) and \( m \), representing the number of vertices and edges, respectively.
The next two lines contain \( n \) positive integers each, representing the initial values \( a_i \) and the target values \( b_i \).
The next \( m \) lines contain two integers \( u \) and \( v \), indicating that there is an edge between vertex \( u \) and vertex \( v \). The graph is guaranteed to be connected and does not have self-loops or multiple edges.

Output Format

For each test case, the first line should output a string. If it is possible to transform the initial values to the target values, output Yes; otherwise, output No. Do not include any other characters on this line, as it may cause the checker to judge it as incorrect.
The second line should output an integer \( k \) (\( k \le 4n \)), indicating the total number of steps in the construction plan.
The next \( k \) lines should each contain four integers \( x, y, z, c \) satisfying \( 1 \le x, y, z \le n \), \( |c| \le 10^{18} \), and \( (x, y), (y, z) \in E \), indicating \( a_x \gets a_x + c, a_y \gets a_y - 2c, a_z \gets a_z + c \).

This problem uses a Special Judge. If there are multiple correct answers, any one of them will be accepted.

Sample Input and Output

Sample Input #1

3
7 6
8 6 0 6 1 1 10 
5 6 2 9 1 2 7 
1 2
2 3
3 4
4 5
5 6
6 7
7 6
8 6 0 6 1 0 11 
5 6 2 9 1 2 7 
1 2
2 3
3 4
4 5
5 6
6 7
7 6
8 6 0 6 1 1 10 
5 6 2 9 1 2 6 
1 2
2 3
3 4
4 5
5 6
6 7

Sample Output #1

Yes
5
7 6 5 -3
6 5 4 -5
5 4 3 -7
4 3 2 -6
3 2 1 -3
No
No

Sample Input #2

2
6 6
10 -3 4 21 -2 11 
4 4 8 8 8 9 
1 2
2 3
3 4
4 5
5 6
6 1
6 6
10 -3 4 21 -2 11 
4 4 8 8 9 8 
1 2
2 3
3 4
4 5
5 6
6 1

Sample Output #2

Yes
6
6 1 2 6
1 2 3 1
2 3 4 3
3 4 5 9
4 5 6 2
5 6 1 5
No

Sample Input #3

1
6 9
7 5 68 16 2 45
42 11 42 17 14 17
1 3
1 4
1 6
1 5
1 2
2 5
2 3
4 6
5 6

Sample Output #3

Yes
10
1 4 6 1
1 6 4 -6
2 1 4 -9
1 3 2 -17
5 1 4 25
2 1 6 32
1 6 5 33
4 1 3 39
4 6 5 -46
3 1 6 -99

Notes/Hints

This problem uses multiple test cases and subtask evaluation.

For \( 100\% \) of the data, it is guaranteed that \( 1 \le T \le 5 \times 10^4 \), \( 3 \le n \le 5 \times 10^5 \), \( n-1 \le m \le 5 \times 10^5 \), \( \sum n, \sum m \le 5 \times 10^5 \), \( |a_i|, |b_i| \le 10^7 \).

Tip: For some data points \( T \le 5 \), the data is difficult to generate. Seeing only a few points wrong does not necessarily mean your algorithm is incorrect. Please carefully consider the correctness of your algorithm.

见题面 Input 部分

见题面 Output 部分