Baltic Olympiad in Informatics: 2013 Day 1, Problem 3

The city of Hotham is once again attacked by its most prominent villain, the Jester. This time his target is Hotham's water supply. The fresh water of Hotham is stored in $N$ reservoirs, which are connected by a set of $M$ pipes. There is at least one path (potentially consisting of several pipes) from any reservoir to any other reservoir. Moreover, every pipe connects two different reservoirs, and there is at most one pipe between any pair of reservoirs.

The Jester has breached some of the pipes and has been draining water from them. Following his playful nature, the Jester ensured that water drained from any one pipe amounts to an even number of cubic meters per second ($m^3/s$). If $2d$ $m^3/s$ of water is drained from a pipe joining reservoirs $u$ and $v$, then $u$ and $v$ lose $d$ $m^3/s$ of water each.

To make matters more confusing, the Jester actually pumps water into some of the breached pipes instead of draining from them. Again, the water pumped into any one pipe is an even number of $m^3/s$. If $2p$ $m^3/s$ of water is pumped into a pipe joining reservoirs $u$ and $v$, then $u$ and $v$ gain $p$ $m^3/s$ of water each. The net change of water volume in each reservoir is the total sum of gains and losses acquired from the pipes connected to it. Formally, if a reservoir is connected to pipes from which $2d_1,2d_2,\dots ,2d_a$ $m^3/s$ of water is drained and to pipes into which $2p_1,2p_2,\dots ,2p_b$ $m^3/s$ of water is pumped, then the net change of water volume in this reservoir is $p_1+p_2+\cdots +p_b-d_1-d_2-\cdots -d_a$ $m^3/s$.

The mayor of Hotham has installed sensors in the reservoirs, but not in the pipes. Therefore, he can observe the net change of water in each reservoir but does not how much water is drained from or pumped into each pipe.

Your task is to write a program that helps the mayor. Given full information about the reservoir network and the net changes in each reservoir, your program should decide if this information is enough to uniquely determine the Jester's plan. The plan can be determined uniquely if there is exactly one possibility for how much water is drained from or pumped into each pipe. Note that these amounts of water need not be the same for all pipes. If there is exactly one possibility, your program should print it.

Constraints

$1\le N\le {10}^5$

$1\le M\le 5\times {10}^5$

$|c_i|\le {10}^9$

If the Jester's plan can be determined uniquely, $|x_i|\le {10}^9$.

Subtask 1 [30%]

The water network of Hotham is a tree.

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line of the input contains two space-separated integers: $N$, the number of reservoirs in Hotham, and $M$, the number of pipes.

The following $N$ lines contain an integer $c_i$ each: the net change in reservoir $i$ $(1\le i\le N)$. Line $i$ of these $N$ lines contains $c_i$.

The following $M$ lines contain two space-separated integers $u_i$ and $v_i$ each $(1\le i\le M)$. Each such line indicates that there is a pipe between reservoirs $u_i$ and $v_i$ $(1\le u_i,v_i\le N)$. Line $i$ of these $M$ lines contains $u_i$ and $v_i$.

The input always describes a set of reservoir changes that can be realized by the Jester.

Output Specification

If the Jester's plan cannot be determined uniquely, your program should output a single line containing $0$. Otherwise, your program should output $M$ lines with one integer $x_i$ each $(1\le i\le M)$. Line $i$ should contain $x_i$. If the Jester drains $d_i$ $m^3/s$ of water from the pipe between $u_i$ and $v_i$, let $x_i=-d_i$.

If the Jester pumps $p_i$ $m^3/s$ of water into the pipe between $u_i$ and $v_i$, let $x_i=p_i$. If the Jester does not add or remove water from the pipe between $u_i$ and $v_i$, let $x_i=0$.

Sample Input 1

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

Sample Output 1

2
-6
2

Sample Input 2

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

Sample Output 2

0