P4938 War1

As the `XM` war is approaching, the `ENLIGHTENED` headquarters, in order to withstand the attack from `RESISTANCE`, adjusted the energy value of a `Portal` in some place so that it can take more hits.

`ENLIGHTENED` headquarters has $N$ `Portal`s, numbered from $1$ to $N$. The initial energy value of `Portal` $i$ is $A_i$. There are $M$ `LINK`s between the `Portal`s. Each `LINK` connects two different `Portal`s. The two connected `Portal`s can transfer energy to each other. Each `Portal` can transfer at most a total of $A_i$ energy to the `Portal`s connected to it. Now, the `ENLIGHTENED` operation commander wants the energy value of each `Portal` $i$ to become at least $B_i$, but he does not know whether this is possible, so he asked you. If it is possible, you need to find one feasible energy transfer plan. **Energy can only be transferred directly, not indirectly.**

The first line contains two integers $N, M$. The second line contains $N$ integers, where the $i$-th integer represents $A_i$. The third line contains $N$ integers, where the $i$-th integer represents $B_i$. Then follow $M$ lines. Each line contains two integers $X, Y$, indicating that there is a `LINK` between `Portal` $X$ and `Portal` $Y$.

If there is a feasible plan, output `YES`, followed by $N$ lines, each containing $N$ integers. The number in row $i$ and column $j$ represents the amount of energy transferred from `Portal` $i$ to `Portal` $j$. If $i = j$, output the amount of energy remaining in `Portal` $i$ after transfers. If there are multiple feasible plans, output any one of them. If there is no feasible plan, output `NO`.

For $20\%$ of the testdata, $N \leq 10$. For $40\%$ of the testdata, $N \leq 25$. For $60\%$ of the testdata, $N \leq 50$. For $100\%$ of the testdata, $N \leq 100$, $M \leq 2 * N$, and $0 \leq A_i, B_i \leq 100$. Translated by ChatGPT 5