Problem Description

Given an undirected graph with $N$ vertices and $M$ edges, the graph is guaranteed to be connected. Each vertex currently contains some amount of water. Now, you can perform an operation on an edge:

• Let water flow out: given $d$, suppose the length is $m$ and the flow time is $s$, then the total water loss rate is $\dfrac{2dm^3}{s}$, and the water loss rate at each endpoint of this edge is $\dfrac{dm^3}{s}$.
• Let water flow in: given $p$, suppose the length is $m$ and the flow time is $s$, then the total water gain rate is $\dfrac{2pm^3}{s}$, and the water gain rate at each endpoint of this edge is $\dfrac{pm^3}{s}$.

Now given this graph and the rate of change of water amount at each vertex, find a construction scheme for the rate of change of water amount on each edge.

Input Format

The first line contains two integers $N,M$, representing the number of vertices and edges.
The $N$ vertices are numbered from $1$ to $N$.
The next $N$ lines each contain an integer $c_i$, representing the rate of change of water amount at this vertex; a positive value means gaining water, and a negative value means losing water.
The next $M$ lines each contain two integers describing an edge.

Output Format

If no such construction scheme exists, or if there are multiple solutions, output only one integer 0.
If such a scheme exists, output $M$ lines, each containing an integer representing the rate of change of water amount on each edge.
Gaining water is positive, losing water is negative.

4 3
-1
1
-3
1
1 2
1 3
1 4

2
-6
2

4 5
1
2
1
2
1 2
2 3
3 4
4 1
1 3

0

Hint

Constraints

For $100\%$ of the testdata, $1 \le N \le 10^5$, $1 \le M \le 5 \times 10^5$, $-10^9 \le c_i \le 10^9$. If a solution exists and is unique, each answer is within $[-10^9,10^9]$.
For $30\%$ of the testdata, the graph is a tree.

Notes

Translated from BalticOI 2013 Day1 C Pipes.

Translated by ChatGPT 5