P7951 [✗✓OI R1] The Fire of the Right

> "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.

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.**

**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.

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.**

**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$. | subtask | $n,m,T$ | Special Properties | Score | | :----------: | :----------: | :-----------: | :-----------: | | 1 | $n,m\le 20$，$T \le 5$ | None | 10 | | 2 | $m=n-1$ | The $i$-th edge connects vertices $i$ and $(i+1)$ | 5 | | 3 | $m=n-1$ | The $i$-th edge connects vertices $1$ and $(i+1)$ | 5 | | 4 | $m=n-1$ | None | 10 | | 5 | $m=n$ | The graph is guaranteed to be a cycle | 10 | | 6 | $n,m\le 200,T \le 5$ | None | 10 | | 7 | $ n,m\le 2000,T \le 5$ | None | 20 | | 8 | | None | 30 | **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