CF1557D.Ezzat and Grid

Moamen was drawing a grid of $n$ rows and $10^9$ columns containing only digits $0$ and $1$. Ezzat noticed what Moamen was drawing and became interested in the minimum number of rows one needs to remove to make the grid beautiful.

A grid is beautiful if and only if for every two consecutive rows there is at least one column containing $1$ in these two rows.

Ezzat will give you the number of rows $n$, and $m$ segments of the grid that contain digits $1$. Every segment is represented with three integers $i$, $l$, and $r$, where $i$ represents the row number, and $l$ and $r$ represent the first and the last column of the segment in that row.

For example, if $n = 3$, $m = 6$, and the segments are $(1,1,1)$, $(1,7,8)$, $(2,7,7)$, $(2,15,15)$, $(3,1,1)$, $(3,15,15)$, then the grid is:

Your task is to tell Ezzat the minimum number of rows that should be removed to make the grid beautiful.

莫阿门正在绘制一个包含 $n$ 行、$10^9$ 列的网格，其中仅包含数字 $0$ 和 $1$。埃扎特注意到了莫阿门所画的内容，并对使该网格变为“优美”所需删除的最少行数产生了兴趣。

当且仅当对于任意两个相邻的行，都存在至少一列，使得该列在这两行中均为 $1$ 时，该网格被称为优美的。

埃扎特将为你提供行数 $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)$，则该网格如下所示：

你的任务是告诉埃扎特：为使该网格变为优美的，所需删除的最少行数。

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 3\cdot10^5$).

Each of the next $m$ lines contains three integers $i$, $l$, and $r$ ($1 \le i \le n$, $1 \le l \le r \le 10^9$). Each of these $m$ lines means that row number $i$ contains digits $1$ in columns from $l$ to $r$, inclusive.

Note that the segments may overlap.

第一行包含两个整数 $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$。

注意：这些区间可能相互重叠。

In the first line, print a single integer $k$ — the minimum number of rows that should be removed.

In the second line print $k$ distinct integers $r_1, r_2, \ldots, r_k$, representing the rows that should be removed ($1 \le r_i \le n$), in any order.

If there are multiple answers, print any.

第一行输出一个整数 $k$ —— 应删除的最少行数。

第二行输出 $k$ 个互不相同的整数 $r_1, r_2, \ldots, r_k$，表示应删除的行（$1 \le r_i \le n$），顺序任意。

如有多个答案，输出任意一个即可。

In the first test case, the grid is the one explained in the problem statement. The grid has the following properties:

1. The $1$-st row and the $2$-nd row have a common $1$ in the column $7$.
2. The $2$-nd row and the $3$-rd row have a common $1$ in the column $15$.

As a result, this grid is beautiful and we do not need to remove any row.

In the second test case, the given grid is as follows:

在第一个测试用例中，网格即为题目描述中所解释的网格。该网格具有以下性质：

1. 第 $1$ 行与第 $2$ 行在第 $7$ 列有一个共同的 $1$。
2. 第 $2$ 行与第 $3$ 行在第 $15$ 列有一个共同的 $1$。

因此，该网格是“优美的”，我们无需删除任何行。

在第二个测试用例中，给定的网格如下所示：