← 返回题目列表

Codeforces · 901/D

D. 给树加权

中文机器翻译题面 查看原题

给定一个具有 n 个顶点和 m 个边的连通无向图。顶点从 1 到 n 进行枚举。

给定 n 个整数 c1, c2, ..., cn,每个整数都在 - n 和 n 之间(包含 - n 和 n)。还保证cv的奇偶性等于顶点v的度的奇偶性。顶点的度是与其连接的边的数量。

你要在每条边上写一个介于 - 2·n2 和 2·n2 (含)之间的权重,使得对于每个顶点 v,连接到该顶点的边上的权重总和等于 cv,或者确定这是不可能的。

输入

第一行包含两个整数 n 和 m (2 ≤ n ≤ 105, n - 1 ≤ m ≤ 105) - 顶点数和边数。

下一行包含 n 个整数 c1, c2, ..., cn (- n ≤ ci ≤ n),其中 ci 是连接到顶点 i 的边所需的权重总和。保证ci的奇偶性等于顶点i的度的奇偶性。

接下来的 m 行描述了图的边缘。这些行中的第 i 行包含两个整数 ai 和 bi(1 ≤ ai,bi ≤ n;ai ≠ bi),这意味着第 i 条边连接顶点 ai 和 bi。

保证给定的图是连通的并且不包含循环和多重边。

输出

如果没有解决方案,则打印“NO”。

否则打印“YES”,然后打印m行,其中第i行是第i条边wi的权重(- 2·n2 ≤ wi ≤ 2·n2)。

示例

输入 #1

3 3
2 2 2
1 2
2 3
1 3

输出 #1

YES
1
1
1

输入 #2

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

输出 #2

YES
-1
1
1

输入 #3

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

输出 #3

YES
3
5
3
-1
-3
5

输入#4

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

输出#4

NO