F. Мадока и первая сессия
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

О нет, на первой же сессии Мадоке попался билет со следующей сложной задачей:

Дано число $$$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$$$. И если возможно, то как это сделать.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 10000, 1 \leq m \leq 10000$$$) — длина массива $$$a$$$ и количество пар чисел.

Вторая строка содержит $$$n$$$ целых чисел $$$s_1, s_2, \ldots s_n$$$ ($$$0 \le s_i \le 1$$$) — элементы массива $$$s$$$.

Третья строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$|a_i| \leq m$$$) — элементы массива $$$a$$$. Гарантируется, что если $$$s_i = 0$$$, то $$$a_i = 0$$$.

$$$i$$$-я из следующих $$$m$$$ строк содержат два целых числа $$$v_i$$$ и $$$u_i$$$ ($$$1 \leq v_i, u_i \leq n, v_i \ne u_i$$$) — индексы элементов массива $$$b$$$, к которым применяется операция. Также гарантируется, что не существует таких двух индексов $$$i$$$ и $$$j$$$, где $$$1 \le i < j \le m$$$, что $$$(v_i, u_i) = (v_j, u_j)$$$ или $$$(v_i, u_i) = (u_j, v_j)$$$.

Выходные данные

Выведите в первой строке «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)$$$. Если существует несколько способов получить правильный ответ, можно вывести любой из них.

Пары можно выводить в любом порядке.

Примеры
Входные данные
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
Входные данные
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
Входные данные
4 4
1 1 1 1
0 2 -2 2
1 3
1 4
2 3
2 4
Выходные данные
NO
Примечание

В первом примере массив $$$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$$$.

В третьем примере входных данных нельзя выполнить операции нужным образом.