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.

Input

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.

Output

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