← 返回题目列表

Codeforces · 1045/A

A. 最后的机会

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

现在是 2969 年。距离登月已经过去 1000 年了。与此同时,人类在超空间™上殖民并和谐相处。

直到我们意识到我们并不孤单。

距离地球不远,庞大的外星人飞船舰队正准备攻击地球。一段时间以来,人类第一次面临真正的危险。危机和恐慌无处不在。来自太阳系各地的科学家们开会讨论了可能的解决方案。然而,没有取得任何进展。

地球最后的希望就是你!

幸运的是,地球配备了MDCS制造的非常强大的防御系统。有$$$N$$$外星人的宇宙飞船排成一列。防御系统由三种类型的武器组成:

- SQL 火箭 – 每个 SQL 火箭最多可以摧毁给定集合中的一艘宇宙飞船。
- 认知光束 – 每个认知光束都有一个间隔 $$$[l,r]$$$ 并且可以在该间隔内摧毁最多一艘宇宙飞船。
- OMG 火箭筒 – 每个 OMG 火箭筒都有三个可能的目标,但是,每个火箭筒可以摧毁零艘或恰好两艘宇宙飞船。此外,由于智能瞄准系统的原因,任何两个不同的 OMG 火箭筒的三个可能目标的集合是不相交的(这意味着每艘船最多有一个 OMG 火箭筒瞄准)。

你的任务是制定一个攻击计划,摧毁尽可能多的宇宙飞船。每一艘被摧毁的宇宙飞船都应该用一种武器摧毁。

输入

第一行包含两个整数:你的武器数量 $$$N$$$ $$$(1\leq N\leq 5000)$$$ 和宇宙飞船数量 $$$M$$$ $$$(1\leq M\leq 5000)$$$。

在接下来的 $$$N$$$ 行中,每一行都以一个表示类型的整数开头(0、1 或 2)。如果类型为 0,则武器是 SQL 火箭,该行的其余部分包含严格正数 $$$K$$$ $$$(\sum{K} \leq 100 000)$$$ 和 $$$k_i$$$ $$$(1\leq k_i\leq M)$$$ 个 $$$K$$$ 整数。如果类型为 1,则武器为认知光束,该行的其余部分包含整数 $$$l$$$ 和 $$$r$$$ $$$(1\leq l\leq r\leq M)$$$。如果类型为 2,则武器为 OMG 火箭筒,该行的其余部分包含不同的数字 $$$a$$$、$$$b$$$ 和 $$$c$$$ $$$ (1 \leq a,b,c \leq M)$$$。

输出

第一行应包含被摧毁的宇宙飞船的最大数量 - $$$X$$$。

在接下来的$$$X$$$行中,每行应包含两个数字$$$A$$$和$$$B$$$,其中$$$A$$$是武器的索引,$$$B$$$是被武器$$$A$$$摧毁的宇宙飞船的索引。

示例

输入 #1

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

输出 #1

4
2 1
3 2
1 4
2 5

注意

SQL火箭只能摧毁第四艘宇宙飞船。 OMG 火箭筒可以摧毁第 1、第 4 或第 5 艘宇宙飞船中的两艘,而认知光束可以摧毁 $$$[1,4]$$$ 区间内的任何宇宙飞船。摧毁飞船的最大数量为 4 艘,一种可能的计划是 SQL 火箭摧毁第 4 艘飞船,OMG 火箭筒摧毁第 1 艘和第 5 艘飞船,认知光束摧毁第 2 艘飞船。