Ezzat and Grid

题意翻译

* 有一个 $n$ 行 $10^9$ 列的表格。 * dead_X 会执行 $m$ 次操作，每次操作会将第 $i$ 行的第 $[l,r]$ 格涂黑。 * dead_X 想知道，至少删掉几行后，对于每相邻的两行，都存在**至少一列**，使得这两行的这一列都涂黑了。 * $n,m\leq3\times 10^5$，一个格子可能被涂黑多次。

题目描述

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.

输出格式

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.

输入输出样例

输入样例 #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

说明

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: