Monocarp 玩一款名为“妖精与侏儒”的电脑游戏。在这款游戏中,他管理着一座由侏儒组成的大型地下城市,并保卫它免受成群的妖精的侵害。
这座城市由 $$$n$$$ 大厅和 $$$m$$$ 连接它们的单向隧道组成。隧道的结构具有以下性质:如果妖精离开任何大厅,他就无法返回该大厅。
城市将受到 $$$k$$$ 波地精的攻击;在第 $$$i$$$ 波中,$$$i$$$ 地精袭击了这座城市。 Monocarp 的目标是通过所有 $$$k$$$ 波浪。
第$$$i$$$波的流程如下:首先,$$$i$$$地精出现在城市的一些大厅中并进行掠夺;每个大厅最多出现一只哥布林。然后,妖精开始沿着隧道移动,掠夺路径上的所有大厅。
妖精非常贪婪和狡猾,所以它们会选择自己的路径,以免两个妖精穿过同一个大厅。在所有可能的攻击计划中,他们选择了一个可以让他们掠夺最多大厅的计划。哥布林掠夺完毕后,就会离开城市。
如果所有大厅都在浪潮中被掠夺 — Monocarp 输掉了比赛。否则,城市就会恢复。如果某个大厅在一轮中被掠夺,那么地精在下一波中仍然有兴趣掠夺它。
在每一波之前,Monocarp 可以花一些时间进行准备。 Monocarp对他的准备没有任何严格的时间限制(他自己决定何时调用每一波),但是他准备一波的时间越长,他通过它获得的分数就越少。如果 Monocarp 为第 $$$i$$$ 波做好 $$$t_i$$$ 分钟的准备,那么他会因通过它而获得 $$$\max(0, x_i - t_i \cdot y_i)$$$ 积分(显然,如果他在此过程中没有失败的话)。
在准备波浪时,Monocarp 可以堵塞隧道。他可以花一分钟的时间来封锁从某个大厅通向的所有隧道,或者封锁通往某个大厅的所有隧道。如果 Monocarp 在准备波浪时堵塞了隧道,那么在下一波波浪中它也会保持堵塞状态。
帮助 Monocarp 抵御所有 $$$k$$$ 波的妖精并获得尽可能多的积分!
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 50$$$; $$$0 \le m \le \frac{n(n - 1)}{2}$$$; $$$1 \le k \le n - 1$$$) — 城市中的大厅数量、隧道数量以及相应的妖精波数。
接下来的 $$$m$$$ 行描述了隧道。第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$)。这意味着隧道从$$$u_i$$$大厅到$$$v_i$$$大厅。隧道的结构具有以下性质:如果妖精离开任何大厅,他就无法返回该大厅。每对大厅之间最多有一条隧道。
接下来的 $$$k$$$ 行描述了评分系统。第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i \le 10^9$$$; $$$1 \le y_i \le 10^9$$$)。如果 Monocarp 为第 $$$i$$$ 波做好 $$$t_i$$$ 分钟的准备,那么他会因通过该波而获得 $$$\max(0, x_i - t_i \cdot y_i)$$$ 积分。
输出
按以下格式打印最优 Monocarp 策略:
首先,打印一个整数 $$$a$$$ ($$$k \le a \le 2n + k$$$) — Monocarp 将执行的操作数。接下来,按照 Monocarp 执行操作的顺序打印操作本身。第 $$$i$$$ 个操作由单个整数 $$$b_i$$$ ($$$-n \le b_i \le n$$$) 描述,格式如下:
- 如果 $$$b_i > 0$$$ 则 Monocarp 会封锁所有从大厅 $$$b_i$$$ 出去的隧道;
- 如果 $$$b_i < 0$$$ 则 Monocarp 会封锁所有进入大厅的隧道 $$$|b_i|$$$;
- 如果 $$$b_i = 0$$$ 那么 Monocarp 会召唤下一波妖精。
您不能多次重复相同的块操作$$$b_i$$$。 Monocarp 必须在他召唤的所有波浪中幸存下来(妖精不应该能够掠夺所有大厅)。 Monocarp 应该准确地跟注 $$$k$$$ 波并获得最大可能的总点数。
如果有多个最佳策略 - 打印其中任何一个。
示例
输入 #1
5 4 4 1 2 2 3 4 3 5 3 100 1 200 5 10 10 100 1
输出 #1
6 -2 -3 0 0 0 0
输入 #2
5 4 4 1 2 2 3 4 3 5 3 100 100 200 5 10 10 100 1
输出 #2
6 0 -3 0 0 1 0
输入 #3
5 10 1 1 2 1 3 1 4 1 5 5 2 5 3 5 4 4 2 4 3 2 3 100 100
输出 #3
6 1 2 3 4 5 0
注意
在第一个示例中,Monocarp 首先封锁大厅 $$$2$$$ 中的所有隧道,其次 — 大厅 $$$3$$$ 中的所有隧道,然后调用所有波浪。他花了两分钟准备挥动 $$$1$$$,因此他获得了 $$$98$$$ 积分。之后他没有准备,这就是为什么他在接下来的每一波中都获得最高分($$$200$$$、$$$10$$$ 和 $$$100$$$)。 Monocarp 总共获得 $$$408$$$ 积分。
在第二个示例中,Monocarp 立即跟注第一波并获得 $$$100$$$ 点。在第二波之前,他封锁了大厅 $$$3$$$ 中的所有隧道。他花了一分钟准备这一波,因此他获得了 $$$195$$$ 积分。 Monocarp 没有为第三波做好准备,因此他通过幸存下来获得 $$$10$$$ 积分。在第四波之前,他封锁了从大厅 $$$1$$$ 出去的所有隧道。他花了一分钟,所以他在第四波中获得了 $$$99$$$ 积分。 Monocarp 总共获得 $$$404$$$ 积分。
在第三个例子中,Monocarp 在这波攻击之前花费多少分钟并不重要,因为他不会因此获得任何分数。这就是为什么他决定封锁城市中的所有隧道,花费 $$$5$$$ 分钟。他在这一波浪潮中幸存下来,但没有得到任何积分。