哦不,第一次考试小圆就遇到了这个难题:
给定整数 $$$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$$$。
第三个例子中,无法按照要求进行操作。