Background

"A mere two billion, a mere two thousand years, is simply not enough."
"The power I have is far more than you think."

You cannot defeat the Fire of the Right.
But to prove that you have a rich imagination, you need to solve a constructive problem.

Problem Description

You are given a connected undirected graph with $n$ vertices and $m$ edges. Each vertex has an initial value $a_i$ and a target value $b_i$. You may perform the following operation on this graph:

• Choose an integer $c$ such that $|c| \le 10^{18}$.
• Choose a path with $3$ vertices and $2$ edges (a chain of length $2$).
• Decrease the value of the middle vertex by $2c$, and increase the values of the other two vertices by $c$ each.

Determine whether it is possible to perform some operations so that finally every vertex value becomes $b_i$. If it is possible, you need to output a sequence of operations, and the number of operations must not exceed $4n$.

Note that $c$ can be negative.

Input Format

This problem has 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,m$, representing the number of vertices and edges.
The next two lines each contain $n$ integers, representing the initial values $a_i$ and the target values $b_i$.
The next $m$ lines each contain two integers $u,v$, meaning there is an edge between vertex $u$ and vertex $v$. The graph is guaranteed to be connected, with no self-loops or multiple edges.

Output Format

For each test case, output a string in the first line. If it is possible to change the initial values into the target values, output Yes; otherwise output No. Do not print any extra characters on the line containing Yes or No, otherwise the checker may judge it as wrong.
In the second line, output an integer $k(k\le4n)$, meaning the constructed plan has $k$ steps.
Then output $k$ lines. Each line contains four integers $x,y,z,c$ satisfying $1 \le x,y,z \le n$, $|c| \le 10^{18}$, $(x,y),(y,z)\in E$, meaning $a_x \gets a_x+c,a_y \gets a_y-2c,a_z \gets a_z+c$.

This problem uses Special Judge. If there are multiple valid answers, output any one.

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

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

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

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

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

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

Hint

This problem uses multiple test cases and subtask-based judging.

For $100\%$ of the data, $1\le T \leq 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 \leq 5\times 10^5$, $|a_i|,|b_i| \leq 10^7$.

Friendly reminder: for some test points, $T \le 5$, so the testdata is relatively hard to construct. If you only get WA on a few points, it does not mean your algorithm is wrong. Please think carefully about the correctness of your algorithm.

Translated by ChatGPT 5