CF1045A Last chance

公元 2969 年。距离人类首次登月已经过去了 1000 年。在这期间，人类已经殖民了“超空间”，并一直和谐共处。 直到我们发现，我们并不孤单。 距离地球不远处，外星人的庞大舰队正准备进攻地球。人类第一次真正陷入危机。危机与恐慌无处不在。来自太阳系各地的科学家们齐聚一堂，讨论可能的解决方案。然而，始终没有取得进展。 地球最后的希望就是你！ 幸运的是，地球装备了由 MDCS 制造的极其强大的防御系统。有 $N$ 艘外星飞船排成一行。防御系统由三种武器组成： - SQL 火箭 —— 每枚 SQL 火箭可以摧毁给定集合中的至多一艘飞船。 - Cognition 光束 —— 每道 Cognition 光束有一个区间 $[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$ 个整数 $k_i$ $(1\leq k_i\leq M)$，表示该火箭可以摧毁的飞船编号。如果类型为 1，则该武器为 Cognition 光束，接下来是两个整数 $l$ 和 $r$ $(1\leq l\leq r\leq M)$，表示可以摧毁区间 $[l, r]$ 内的任意一艘飞船。如果类型为 2，则该武器为 OMG 火箭筒，接下来是三个互不相同的整数 $a$、$b$、$c$ $(1\leq a, b, c \leq M)$，表示三个可能的目标。

第一行输出最大可摧毁飞船数 $X$。 接下来的 $X$ 行，每行输出两个整数 $A$ 和 $B$，表示第 $A$ 个武器摧毁了第 $B$ 艘飞船。

SQL 火箭只能摧毁第 4 号飞船。OMG 火箭筒可以摧毁第 1、4、5 号飞船中的任意两艘。Cognition 光束可以摧毁区间 $[1,4]$ 内的任意一艘飞船。最大可摧毁飞船数为 4，一种可行方案是：SQL 火箭摧毁第 4 号飞船，OMG 火箭筒摧毁第 1 号和第 5 号飞船，Cognition 光束摧毁第 2 号飞船。 由 ChatGPT 4.1 翻译