D. Взвешивание графа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан cвязный неориентированный граф, состоящий из n вершин и m ребер. Будем считать, что вершины графа пронумерованы целыми числами от 1 до n.

Вам даны n целых чисел c1, c2, ..., cn, каждое из них находится в пределах от  - 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-й из этих строк должно содержаться одно целое число wi ( - 2·n2 ≤ wi ≤ 2·n2) – вес i-го ребра.

Примеры
Входные данные
3 3
2 2 2
1 2
2 3
1 3
Выходные данные
YES
1
1
1
Входные данные
4 3
-1 0 2 1
1 2
2 3
3 4
Выходные данные
YES
-1
1
1
Входные данные
6 6
3 5 5 5 1 5
1 4
3 2
4 3
4 5
3 5
5 6
Выходные данные
YES
3
5
3
-1
-3
5
Входные данные
4 4
4 4 2 4
1 2
2 3
3 4
4 1
Выходные данные
NO