CF1717F.Madoka and The First Session

Oh no, on the first exam Madoka got this hard problem:

Given integer $n$ and $m$ pairs of integers ($v_i, u_i$). Also there is an array $b_1, b_2, \ldots, b_n$, initially filled with zeros.

Then for each index $i$, where $1 \leq i \leq m$, perform either $b_{v_i} := b_{v_i} - 1$ and $b_{u_i} := b_{u_i} + 1$, or $b_{v_i} := b_{v_i} + 1$ and $b_{u_i} := b_{u_i} - 1$. Note that exactly one of these operations should be performed for every $i$.

Also there is an array $s$ of length $n$ consisting of $0$ and $1$. And there is an array $a_1, a_2, \ldots, a_n$, where it is guaranteed, that if $s_i = 0$ holds, then $a_i = 0$.

Help Madoka and determine whenever it is possible to perform operations in such way that for every $i$, where $s_i = 1$ it holds that $a_i = b_i$. If it possible you should also provide Madoka with a way to perform operations.

糟糕，魔法少女小圆第一次考试就遇到了这道难题：

给定整数 $n$ 和 $m$ 对整数 $(v_i, u_i)$。另有一个长度为 $n$ 的数组 $b_1, b_2, \ldots, b_n$，初始时所有元素均为 $0$。

接着，对每个下标 $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$，必须且仅能选择上述两种操作中的一种执行。

此外，还有一个长度为 $n$ 的由 $0$ 和 $1$ 组成的数组 $s$，以及一个数组 $a_1, a_2, \ldots, a_n$，满足如下条件：若 $s_i = 0$，则必有 $a_i = 0$。

请帮助小圆判断：是否存在一种操作方式，使得对每个满足 $s_i = 1$ 的下标 $i$，均有 $a_i = b_i$？若存在，请同时给出一种可行的操作方案。

The first line contains two integers $n$ and $m$ ($2 \leq n \leq 10000, 1 \leq m \leq 10000$) — the length of the array $a$ and the number of pair of integers.

The second line contains $n$ integers $s_1, s_2, \ldots s_n$ ($0 \le s_i \le 1$) — the elements of the array $s$.

The third line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($|a_i| \leq m$) — the elements of the array $a$. It is guaranteed that if $s_i = 0$ holds, then $a_i = 0$.

$i$-th of the following $m$ lines contains two integers $v_i$ and $u_i$ ($1 \leq v_i, u_i \leq n, v_i \ne u_i$) — the indexes of the elements of the array $b$ to which the operation is performed. It is also guaranteed that there are no two indices $i$ and $j$, where $1 \le i \lt j \le m$, such that $(v_i, u_i) = (v_j, u_j)$ or $(v_i, u_i) = (u_j, v_j)$.

第一行包含两个整数 $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$。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $v_i$ 和 $u_i$（$1 \leq v_i, u_i \leq n,\ v_i \ne u_i$）—— 表示对数组 $b$ 中下标为 $v_i$ 和 $u_i$ 的元素执行操作。此外还保证：不存在满足 $1 \le i < j \le m$ 的两个下标 $i$ 和 $j$，使得 $(v_i, u_i) = (v_j, u_j)$ 或 $(v_i, u_i) = (u_j, v_j)$。

In the first line print "YES" if it is possible to perform operations in the required way, and "NO" otherwise.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

In case you printed "YES", print $m$ pairs of integers. If for pair $(v_i, u_i)$ we should perform $b_{v_i} := b_{v_i} - 1$ and $b_{u_i} := b_{u_i} + 1$, print $(v_i, u_i)$. Otherwise print $(u_i, v_i)$. If there are multiple ways to get the correct answer, you can print any of them.

You can print pairs in any order.

第一行输出“YES”（如果可以按要求的方式执行操作），否则输出“NO”。

每个字母的大小写不限（例如，“YES”、“Yes”、“yes”、“yEs”均被视为肯定回答）。

若你输出了“YES”，则接下来输出 $m$ 对整数。对于第 $i$ 对 $(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)$。若存在多种可行方案，输出任意一种即可。

各对整数的输出顺序不限。

In the first example, the array $b$ will change as follows: $[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$ for all indices $i$ from $1$ to $5$.

In the second example, it is enough for us that $b_2 = 1$ at the end, since only $s_2 = 1$.

In the third example, the operations cannot be performed as required.

在第一个例子中，数组 $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]$。对所有从 $1$ 到 $5$ 的下标 $i$，均有 $a_i = b_i$。

在第二个例子中，只需最终满足 $b_2 = 1$ 即可，因为仅有 $s_2 = 1$。

在第三个例子中，无法按要求执行操作。