Weighting a Tree

Description:

Input:

The first line contains two integers n and m (2 ≤ n ≤ 10⁵, n - 1 ≤ m ≤ 10⁵) — the number of vertices and the number of edges.

The next line contains n integers c₁, c₂, ..., 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² ≤ w_i ≤ 2·n²).

Sample Input:

3 3
2 2 2
1 2
2 3
1 3

Sample Output:

YES
1
1
1

Sample Input:

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

Sample Output:

YES
-1
1
1

Sample Input:

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

Sample Output:

YES
3
5
3
-1
-3
5

Sample Input:

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

Sample Output:

NO