CF901D.Weighting a Tree

You are given a connected undirected graph with $n$ vertices and $m$ edges. The vertices are enumerated from $1$ to $n$ .

You are given $n$ integers $c_{1},c_{2},...,c_{n}$ , each of them is between $-n$ and $n$ , inclusive. It is also guaranteed that the parity of $c_{v}$ equals the parity of degree of vertex $v$ . The degree of a vertex is the number of edges connected to it.

You are to write a weight between $-2·n^{2}$ and $2·n^{2}$ (inclusive) on each edge in such a way, that for each vertex $v$ the sum of weights on edges connected to this vertex is equal to $c_{v}$ , or determine that this is impossible.

The first line contains two integers $n$ and $m$ ( $2<=n<=10^{5}$ , $n-1<=m<=10^{5}$ ) — the number of vertices and the number of edges.

The next line contains $n$ integers $c_{1},c_{2},...,c_{n}$ ( $-n<=c_{i}<=n$ ), where $c_{i}$ is the required sum of weights of edges connected to vertex $i$ . It is guaranteed that the parity of $c_{i}$ equals the parity of degree of vertex $i$ .

The next $m$ lines describe edges of the graph. The $i$ -th of these lines contains two integers $a_{i}$ and $b_{i}$ ( $1<=a_{i},b_{i}<=n$ ; $a_{i}≠b_{i}$ ), meaning that the $i$ -th edge connects vertices $a_{i}$ and $b_{i}$ .

It is guaranteed that the given graph is connected and does not contain loops and multiple edges.

If there is no solution, print "NO".

Otherwise print "YES" and then $m$ lines, the $i$ -th of them is the weight of the $i$ -th edge $w_{i}$ ( $-2·n^{2}<=w_{i}<=2·n^{2}$ ).