← 返回题目列表

Codeforces · 1557/D

D. 伊扎特和网格

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

Moamen 正在绘制一个由 $$$n$$$ 行和 $$$10^9$$$ 列组成的网格,其中仅包含数字 $$$0$$$ 和 $$$1$$$。埃扎特注意到了莫阿曼正在画的东西,并对一个人需要删除多少行才能使网格变得漂亮产生了兴趣。

网格是漂亮的当且仅当每连续两行中至少有一列包含 $$$1$$$ 。

Ezzat 将为您提供 $$$n$$$ 行数以及包含数字 $$$1$$$ 的网格 $$$m$$$ 段数。每个段都用三个整数 $$$i$$$、$$$l$$$ 和 $$$r$$$ 表示,其中 $$$i$$$ 表示行号,$$$l$$$ 和 $$$r$$$ 表示该行中段的第一列和最后一列。

例如,如果 $$$n = 3$$$、$$$m = 6$$$,并且段为 $$$(1,1,1)$$$、$$$(1,7,8)$$$、$$$(2,7,7)$$$、$$$(2,15,15)$$$、$$$(3,1,1)$$$、 $$$(3,15,15)$$$,则网格为:

你的任务是告诉 Ezzat 为使网格美观而应删除的最少行数。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 3\cdot10^5$$$)。

接下来的 $$$m$$$ 行包含三个整数 $$$i$$$、$$$l$$$ 和 $$$r$$$ ($$$1 \le i \le n$$$、$$$1 \le l \le r \le 10^9$$$)。这些 $$$m$$$ 行中的每一行都表示行号 $$$i$$$ 在从 $$$l$$$ 到 $$$r$$$(含)的列中包含数字 $$$1$$$。

请注意,这些段可能会重叠。

输出

在第一行中,打印一个整数 $$$k$$$ — 应删除的最小行数。

在第二行中打印 $$$k$$$ 不同的整数 $$$r_1, r_2, \ldots, r_k$$$,表示应以任意顺序删除的行 ($$$1 \le r_i \le n$$$)。

如果有多个答案,请打印其中一个。

示例

输入 #1

3 6
1 1 1
1 7 8
2 7 7
2 15 15
3 1 1
3 15 15

输出 #1

0

输入 #2

5 4
1 2 3
2 4 6
3 3 5
5 1 1

输出 #2

3
2 4 5

注意

在第一个测试用例中,网格是问题陈述中解释的网格。网格具有以下属性:

1. $$$1$$$-st 行和 $$$2$$$-nd 行在 $$$7$$$ 列中具有共同的 $$$1$$$。
2. $$$2$$$-nd 行和 $$$3$$$-rd 行在 $$$15$$$ 列中具有共同的 $$$1$$$。

在第二个测试用例中,给定的网格如下: