Madoka and The First Session

题意翻译

给出整数 $n$ 和 $m$ 对整数$(v_i,u_i)$。同时有一个序列 $B$ ,长度为 $n$ ，保证一开始全为 $0$ 。 然后对于每一对 $(v_i,u_i)$，可以执行两种操作中的一种: 1. $b_{v_i}\gets b_{v_i}-1，b_{u_i}\gets b_{u_i}+1$ 2. $b_{v_i}\gets b_{v_i}+1，b_{u_i}\gets b_{u_i}-1$ 然后还会给你两个序列 $A$，$S$ 长度均为 $n$，保证当 $s_i=0$ 时，$a_i=0$ 。 问你在在所有操作方案中，是否有一种可以使得对于任意的 $s_i=1$，都有 $a_i=b_i$。 #### 输入格式 第 $1$ 行两个整数 $n$，$m$。 第 $2$ 行 $n$ 个整数，表示 $S$ 数组。 第 $3$ 行 $n$ 个整数，表示 $A$ 数组。 第 $4\sim n-3$ 行每行 $2$ 个整数，表示 $(u_i,v_i)$。 #### 输出格式 有解的话第一行输出 `YES`，然后下面 $m$ 行如果执行操作 $1$ 就输出 $(v_i,u_i)$，执行操作 $2$ 输出 $(u_i,v_i)$。如果无解则输出`NO`。

题目描述

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.

输入输出格式

输入格式

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 < j \le m $ , such that $ (v_i, u_i) = (v_j, u_j) $ or $ (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.

输入输出样例

输入样例 #1

5 5
1 1 1 1 1
-2 0 2 1 -1
1 5
1 4
3 5
3 4
4 5

输出样例 #1

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

输出样例 #2

YES
1 3
3 5
3 2
4 3
5 4

输入样例 #3

4 4
1 1 1 1
0 2 -2 2
1 3
1 4
2 3
2 4

输出样例 #3

NO

说明

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.

**题目大意：**

给定整数 $ n $ 和 $ m $ 对整数 $(v_i,u_i)$。有一个长度为 $ n $ 的序列 $ B $，初始时全为 $ 0 $。对于每对 $(v_i,u_i)$，有两种操作可选：

1. $ b_{v_i} := b_{v_i} - 1, b_{u_i} := b_{u_i} + 1 $
2. $ b_{v_i} := b_{v_i} + 1, b_{u_i} := b_{u_i} - 1 $

同时给定两个序列 $ A $ 和 $ S $，长度均为 $ n $，保证当 $ s_i = 0 $ 时，$ a_i = 0 $。

要求判断是否存在一种操作方案，使得对于所有 $ s_i = 1 $ 的 $ i $，都有 $ a_i = b_i $。

**输入格式：**

第 1 行：两个整数 $ n $ 和 $ m $。

第 2 行：$ n $ 个整数，表示序列 $ S $。

第 3 行：$ n $ 个整数，表示序列 $ A $。

接下来 $ m $ 行：每行 2 个整数，表示 $(v_i,u_i)$。

**输出格式：**

如果存在解决方案，第一行输出 `YES`，之后 $ m $ 行按照操作执行情况输出对应的 $(v_i,u_i)$ 或 $(u_i,v_i)$。如果无解，则输出 `NO`。**题目大意：** 给定整数 $ n $ 和 $ m $ 对整数 $(v_i,u_i)$。有一个长度为 $ n $ 的序列 $ B $，初始时全为 $ 0 $。对于每对 $(v_i,u_i)$，有两种操作可选： 1. $ b_{v_i} := b_{v_i} - 1, b_{u_i} := b_{u_i} + 1 $ 2. $ b_{v_i} := b_{v_i} + 1, b_{u_i} := b_{u_i} - 1 $ 同时给定两个序列 $ A $ 和 $ S $，长度均为 $ n $，保证当 $ s_i = 0 $ 时，$ a_i = 0 $。 要求判断是否存在一种操作方案，使得对于所有 $ s_i = 1 $ 的 $ i $，都有 $ a_i = b_i $。 **输入格式：** 第 1 行：两个整数 $ n $ 和 $ m $。 第 2 行：$ n $ 个整数，表示序列 $ S $。 第 3 行：$ n $ 个整数，表示序列 $ A $。 接下来 $ m $ 行：每行 2 个整数，表示 $(v_i,u_i)$。 **输出格式：** 如果存在解决方案，第一行输出 `YES`，之后 $ m $ 行按照操作执行情况输出对应的 $(v_i,u_i)$ 或 $(u_i,v_i)$。如果无解，则输出 `NO`。