Задан cвязный неориентированный граф, состоящий из n вершин и m ребер. Будем считать, что вершины графа пронумерованы целыми числами от 1 до n.
Вам даны n целых чисел c1, c2, ..., cn, каждое из них находится в пределах от - n до n, включительно. Также гарантируется, что четность cv совпадает с четностью степени вершины v. Степенью вершины называется число входящих в нее ребер.
В задаче вам требуется поставить каждому ребру вес — целое число от - 2·n2 до 2·n2 (включительно) так, чтобы для каждой вершины v сумма весов входящих в нее ребер была равна cv, или сообщить, что это невозможно.
Выходные данные
Если решения нет, то выведите «NO».
Иначе, выведите «YES» и m строк, в i-й из этих строк должно содержаться одно целое число wi ( - 2·n2 ≤ wi ≤ 2·n2) – вес i-го ребра.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
2 2 2
1 2
2 3
1 3
|
YES
1
1
1
|
|
2
|
4 3
-1 0 2 1
1 2
2 3
3 4
|
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
|
YES
3
5
3
-1
-3
5
|
|
4
|
4 4
4 4 2 4
1 2
2 3
3 4
4 1
|
NO
|