Ezzat and Grid
Description
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.
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.
题面翻译
- 有一个 行 列的表格。
- dead_X 会执行 次操作，每次操作会将第 行的第 格涂黑。
- dead_X 想知道，至少删掉几行后，对于每相邻的两行，都存在至少一列，使得这两行的这一列都涂黑了。
- ，一个格子可能被涂黑多次。
Input
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.
Output
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.
3 6
1 1 1
1 7 8
2 7 7
2 15 15
3 1 1
3 15 15
5 4
1 2 3
2 4 6
3 3 5
5 1 1
0
3
2 4 5
Note
In the first test case, the grid is the one explained in the problem statement. The grid has the following properties:
- The $1$-st row and the $2$-nd row have a common $1$ in the column $7$.
- The $2$-nd row and the $3$-rd row have a common $1$ in the column $15$.
In the second test case, the given grid is as follows:
相关
在下列比赛中: