Background

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.

Problem Description

ENLIGHTENED headquarters has $N$ Portals, numbered from $1$ to $N$. The initial energy value of Portal $i$ is $A_i$. There are $M$ LINKs between the Portals. Each LINK connects two different Portals. The two connected Portals can transfer energy to each other. Each Portal can transfer at most a total of $A_i$ energy to the Portals 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.

Input Format

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

Output Format

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.

3 2 
1 2 3
0 0 6
1 3
2 3

YES
0 0 1
0 0 2
0 0 3 

3 2 
1 2 3
0 0 7
1 3
2 3

NO

Hint

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