В стране есть n городов и m двусторонних дорог между ними. У каждого города есть армия. Армия i-го города состоит из ai солдат. В стране объявлена мобилизация. В результате неё каждый солдат должен либо остаться в своем городе, либо перейти в один из соседних городов, то есть перейти по не более чем одной дороге.
Проверьте, возможно ли, чтобы после перехода в i-м городе было ровно bi солдат.
Выходные данные
Если требуемое невозможно, выведите единственное слово: "NO".
В противном случае выведите слово "YES", а затем выведите n строк, в каждой строке выведите по n целых чисел. Число в i-й строке и j-м столбце должно обозначать, сколько солдат должно перейти из города i в город j (если i ≠ j), либо сколько солдат должно остаться в городе i (если i = j).
Если возможных ответов несколько, выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 2 6 3
3 5 3 1
1 2
2 3
3 4
4 2
|
YES
1 0 0 0
2 0 0 0
0 5 1 0
0 0 2 1
|
|
2
|
2 0
1 2
2 1
|
NO
|