P6755 [BalticOI 2013] Pipes (Day1)

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.

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.

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.

#### 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](https://boi.cses.fi/files/boi2013_day1.pdf). Translated by ChatGPT 5