← 返回题目列表

Codeforces · 1717/F

F. 小圆和第一届会议

中文机器翻译题面 查看原题

哦不,第一次考试小圆就遇到了这个难题:

给定整数 $$$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$$$ 执行这些操作之一。

还有一个长度为 $$$n$$$ 的数组 $$$s$$$,由 $$$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)$$$。如果有多种方法可以获得正确答案,您可以打印其中任何一种。

您可以按任意顺序打印对。

示例

输入 #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
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

输出 #3

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$$$ 对于从 $$$1$$$ 到 $$$5$$$ 的所有指数 $$$i$$$。

在第二个示例中,最后 $$$b_2 = 1$$$ 对我们来说就足够了,因为只有 $$$s_2 = 1$$$。

第三个例子中,无法按照要求进行操作。