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.

给你一个包含 $n$ 个顶点和 $m$ 条边的连通无向图。顶点编号为 $1$ 到 $n$。

给你 $n$ 个整数 $c_1,\,c_2,\,\dots,\,c_n$，每个整数均在 $-n$ 到 $n$（含端点）之间。同时保证：对每个顶点 $v$，$c_v$ 的奇偶性与顶点 $v$ 的度数的奇偶性相同。顶点的度数是指与其相连的边的数量。

你需要给每条边赋予一个权值，该权值需在 $-2\cdot n^2$ 到 $2\cdot n^2$（含端点）之间，使得对每个顶点 $v$，与其相连的所有边上的权值之和恰好等于 $c_v$；若无法做到，则判定为不可能。

The first line contains two integers n and m (2 ≤ n ≤ 105, n - 1 ≤ m ≤ 105) — 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.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$，$n-1 \leq m \leq 10^5$）—— 分别表示顶点数和边数。

第二行包含 $n$ 个整数 $c_1,\,c_2,\,\dots,\,c_n$（$-n \leq c_i \leq n$），其中 $c_i$ 表示与顶点 $i$ 相连的所有边的权重之和。保证每个 $c_i$ 的奇偶性与顶点 $i$ 的度数的奇偶性相同。

接下来的 $m$ 行描述图中的边。其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i,\,b_i \leq n$；$a_i \neq b_i$），表示第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。

保证所给图是连通的，且不含自环和重边。

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

如果无解，输出 "NO"。

否则输出 "YES"，然后输出 m 行，其中第 i 行为第 i 条边的权值 w__i（满足 - 2·_n_² ≤ w__i ≤ 2·_n_²）。