给定一个具有 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