{"raw_statement":[{"iden":"statement","content":"You are given a connected undirected graph with _n_ vertices and _m_ edges. The vertices are enumerated from 1 to _n_.\n\nYou 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.\n\nYou 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."},{"iden":"input","content":"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.\n\nThe 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_.\n\nThe 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_.\n\nIt is guaranteed that the given graph is connected and does not contain loops and multiple edges."},{"iden":"output","content":"If there is no solution, print \"_NO_\".\n\nOtherwise 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)."},{"iden":"examples","content":"Input\n\n3 3\n2 2 2\n1 2\n2 3\n1 3\n\nOutput\n\nYES\n1\n1\n1\n\nInput\n\n4 3\n-1 0 2 1\n1 2\n2 3\n3 4\n\nOutput\n\nYES\n-1\n1\n1\n\nInput\n\n6 6\n3 5 5 5 1 5\n1 4\n3 2\n4 3\n4 5\n3 5\n5 6\n\nOutput\n\nYES\n3\n5\n3\n-1\n-3\n5\n\nInput\n\n4 4\n4 4 2 4\n1 2\n2 3\n3 4\n4 1\n\nOutput\n\nNO"}],"translated_statement":[{"iden":"statement","content":"你被给定一个具有 #cf_span[n] 个顶点和 #cf_span[m] 条边的连通无向图。顶点编号从 #cf_span[1] 到 #cf_span[n]。\n\n你被给定 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]，每个整数介于 #cf_span[ - n] 和 #cf_span[n] 之间（包含两端）。同时保证 #cf_span[cv] 的奇偶性与顶点 #cf_span[v] 的度数的奇偶性相同。顶点的度数是指与其相连的边的数量。\n\n你需要在每条边上写一个介于 #cf_span[ - 2·n2] 和 #cf_span[2·n2] 之间（包含两端）的权重，使得对于每个顶点 #cf_span[v]，与其相连的所有边的权重之和等于 #cf_span[cv]；如果不可能，则判定为无解。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 105]，#cf_span[n - 1 ≤ m ≤ 105]）——顶点数和边数。\n\n下一行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[ - n ≤ ci ≤ n]），其中 #cf_span[ci] 是顶点 #cf_span[i] 所连边的权重之和的期望值。保证 #cf_span[ci] 的奇偶性与顶点 #cf_span[i] 的度数的奇偶性相同。\n\n接下来的 #cf_span[m] 行描述图中的边。第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ n]；#cf_span[ai ≠ bi]），表示第 #cf_span[i] 条边连接顶点 #cf_span[ai] 和 #cf_span[bi]。\n\n保证给定的图是连通的，且不包含自环和重边。\n\n如果无解，请输出 \"_NO_\"。\n\n否则输出 \"_YES_\"，然后输出 #cf_span[m] 行，第 #cf_span[i] 行为第 #cf_span[i] 条边的权重 #cf_span[wi]（#cf_span[ - 2·n2 ≤ wi ≤ 2·n2]）。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 105]，#cf_span[n - 1 ≤ m ≤ 105]）——顶点数和边数。下一行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[ - n ≤ ci ≤ n]），其中 #cf_span[ci] 是顶点 #cf_span[i] 所连边的权重之和的期望值。保证 #cf_span[ci] 的奇偶性与顶点 #cf_span[i] 的度数的奇偶性相同。接下来的 #cf_span[m] 行描述图中的边。第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ n]；#cf_span[ai ≠ bi]），表示第 #cf_span[i] 条边连接顶点 #cf_span[ai] 和 #cf_span[bi]。保证给定的图是连通的，且不包含自环和重边。"},{"iden":"output","content":"如果无解，请输出 \"_NO_\"。否则输出 \"_YES_\"，然后输出 #cf_span[m] 行，第 #cf_span[i] 行为第 #cf_span[i] 条边的权重 #cf_span[wi]（#cf_span[ - 2·n2 ≤ wi ≤ 2·n2]）。"},{"iden":"examples","content":"输入\n3 3\n2 2 2\n1 2\n2 3\n1 3\n输出\nYES\n1\n1\n1\n\n输入\n4 3\n-1 0 2 1\n1 2\n2 3\n3 4\n输出\nYES\n-1\n1\n1\n\n输入\n6 6\n3 5 5 5 1 5\n1 4\n3 2\n4 3\n4 5\n3 5\n5 6\n输出\nYES\n3\n5\n3\n-1\n-3\n5\n\n输入\n4 4\n4 4 2 4\n1 2\n2 3\n3 4\n4 1\n输出\nNO"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be a connected undirected graph with $ n = |V| $ vertices and $ m = |E| $ edges, where $ V = \\{1, 2, \\dots, n\\} $.  \nLet $ d_v $ denote the degree of vertex $ v \\in V $.  \nLet $ c_v \\in \\mathbb{Z} $ be the required sum of edge weights incident to vertex $ v $, with $ -n \\leq c_v \\leq n $ and $ c_v \\equiv d_v \\pmod{2} $ for all $ v \\in V $.  \nLet $ w_e \\in \\mathbb{Z} $ be the weight assigned to edge $ e \\in E $, with $ -2n^2 \\leq w_e \\leq 2n^2 $.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 10^5 $, $ n - 1 \\leq m \\leq 10^5 $  \n2. $ \\sum_{v \\in V} c_v $ is even (implicit from handshaking lemma and parity condition)  \n3. For each vertex $ v \\in V $:  \n   $$\n   \\sum_{e \\in \\delta(v)} w_e = c_v\n   $$  \n   where $ \\delta(v) $ is the set of edges incident to $ v $.\n\n**Objective**  \nDetermine whether there exists an assignment of weights $ \\{w_e\\}_{e \\in E} $ satisfying the above constraints. If yes, output such an assignment; otherwise output \"NO\".","simple_statement":null,"has_page_source":false}