О нет, на первой же сессии Мадоке попался билет со следующей сложной задачей:
Дано число \(n\) и \(m\) пар чисел (\(v_i, u_i\)). А также есть массив \(b_1, b_2, \ldots, b_n\), изначально заполненный нулями.
Затем для каждого индекса \(i\), где \(1 \leq i \leq m\), выполняется либо \(b_{v_i} := b_{v_i} - 1\) и \(b_{u_i} := b_{u_i} + 1\), либо \(b_{v_i} := b_{v_i} + 1\) и \(b_{u_i} := b_{u_i} - 1\). Обратите внимание, что ровно одна из этих операций должна быть выполнена для каждого \(i\).
Также дан массив \(s\) размера \(n\), состоящий только из \(0\) и \(1\). И массив \(a_1, a_2, \ldots, a_n\), где гарантируется, что если \(s_i = 0\), то \(a_i = 0\).
Помогите Мадоке и определите, можно ли выполнить операции выше таким образом, чтобы для каждого \(i\), где \(s_i = 1\), выполнялось \(a_i = b_i\). И если возможно, то как это сделать.
Выходные данные
Выведите в первой строке «YES», если можно выполнить операции нужным образом, и «NO» в противном случае.
Вы можете выводить каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).
В случае, если вы вывели «YES», выведите \(m\) пар целых чисел. Если для пары \((v_i, u_i)\) нужно выполнить \(b_{v_i} := b_{v_i} - 1\) и \(b_{u_i} := b_{u_i} + 1\), выведите \((v_i, u_i)\). Иначе выведите \((u_i, v_i)\). Если существует несколько способов получить правильный ответ, можно вывести любой из них.
Пары можно выводить в любом порядке.
Примечание
В первом примере массив \(b\) будет меняться следующим образом: \([0,0,0,0,0] \rightarrow [-1,0,0,1,0] \rightarrow [-2,0,0,1,1] \rightarrow [-2,0,1,0,1] \rightarrow [-2,0,2,0,0] \rightarrow [-2,0,2,1,-1]\). \(a_i = b_i\) для всех индексов \(i\) от \(1\) до \(5\).
Во втором примере нам достаточно, чтобы в конце \(b_2 = 1\), поскольку только \(s_2 = 1\).
В третьем примере входных данных нельзя выполнить операции нужным образом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5
1 1 1 1 1
-2 0 2 1 -1
1 5
1 4
3 5
3 4
4 5
|
YES
1 5
1 4
5 3
4 3
5 4
|
|
2
|
5 5
0 1 0 1 0
0 1 0 0 0
1 3
2 3
3 5
3 4
4 5
|
YES
3 1
3 2
5 3
3 4
4 5
|
|
3
|
4 4
1 1 1 1
0 2 -2 2
1 3
1 4
2 3
2 4
|
NO
|