P7951 [✗✓OI R1] 右方之火
题目背景
> 「区区二十亿，区区两千年，根本就不够。」
> 「本大爷所拥有的力量可比你想象的还多哦。」
你打不过右方之火。
但是为了证明你的想象力很丰富，你要做一道构造题。
题目描述
你有一个 $n$ 个点 $m$ 条边的无向连通图，每个点有一个初始权值 $a_i$ 以及一个目标权值 $b_i$。现在你可以对这张图进行这样的操作：
- 选择一个整数 $c$，需要满足 $|c| \le 10^{18}$；
- 选一条点数为 $3$，边数为 $2$ 的链；
- 使得中间点的权值减去 $2c$，另外两个点的权值各加上 $c$。
问是否可以进行若干次操作使得最后每个点的权值都为 $b_i$。如果可以，你需要输出方案，操作次数不能超过 $4n$。
**注意 $c$ 可以为负数。**
输入格式
**本题有多组测试数据。**
第一行一个正整数 $T$ ，表示测试数据的数量。
对于每组数据，第一行两个正整数 $n,m$，分别表示点数和边数。
接下来两行，每行各 $n$ 个正整数，表示初始权值 $a_i$ 和目标权值 $b_i$。
接下来 $m$ 行，每行两个整数 $u,v$，表示 $u$ 号点和 $v$ 号点之间有一条边，保证图连通，没有自环和重边。
输出格式
对于每组数据，第一行输出一个字符串，若能够从初始权值变为目标权值，输出 `Yes` ，否则输出 `No`。**输出 `Yes` 和 `No` 的这一行不要有其他奇怪的字符，不然可能会被 checker 判成错误。**
第二行输出一个整数 $k(k\le4n)$，表示构造方案共有 $k$ 步。
接下来 $k$ 行，每行四个整数 $x,y,z,c$ 满足 $1 \le x,y,z \le n$，$|c| \le 10^{18}$，$(x,y),(y,z)\in E$，表示 $a_x \gets a_x+c,a_y \gets a_y-2c,a_z \gets a_z+c$。
**本题采用 Special Judge。如果有多种答案，输出任意一种即可。**
说明/提示
**本题采用多组测试数据，子任务评测。**
对于 $100\%$ 的数据，满足 $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$ | 特殊性质 | 分数
| :----------: | :----------: | :-----------: | :-----------: |
| 1 | $n,m\le 20$，$T \le 5$ | 无 | 10 |
| 2 | $m=n-1$ | 保证第 $i$ 条边连接 $i$ 和 $(i+1)$ 号点 | 5 |
| 3 | $m=n-1$ | 保证第 $i$ 条边连接 $1$ 和 $(i+1)$ 号点 | 5 |
| 4 | $m=n-1$ | 无 | 10 |
| 5 | $m=n$ | 保证图是一个环 | 10 |
| 6 | $n,m\le 200,T \le 5$ | 无 | 10 |
| 7 | $ n,m\le 2000,T \le 5$ | 无 | 20 |
| 8 | | 无 | 30 |
**温馨提示：对于部分数据点 $T \le 5$ 因此数据比较难造，看到只 WA 了少数几个点并不代表你的算法没有问题，请仔细思考算法的正确性。**
