AT_arc045_b [ARC045B] ドキドキデート大作戦高橋君

# 高桥君的心跳约会大作战 高桥君在读的学校即将进行一次大扫除。学校中有N个教室，分别编号为 $1,2,3, \dots ,N$ 。这些教室排成了一排。 高桥君的学校中共有含高桥君在内的 $M$ 个学生，需要扫除的连续教室区间（称为扫除区间）有 $M$ 个。但是，还没有决定由哪个学生来负责哪个扫除区间。不同的学生负责不同的扫除区间，每个学生必须打扫被分配到的所有教室。 $1$ 个教室可能被多个扫除区间包含。 高桥君突然发现，大扫除当天他正好与女同学有约会。无论怎么样高桥君都不想毁掉这次约会，所以只能把大扫除翘掉了。但是高桥君很在意自己会不会暴露：高桥君负责的教室中如果有任何教室没有被打扫，高桥君就会暴露。 你的任务是：替高桥君找出就算翘掉扫除也不会暴露的所有扫除区间。 另外，这所学校里的学生们都非常勤奋努力，故假定除高桥君外的所有人都不会缺席大扫除。

输入按以下标准： $$ N \space M $$ $$ s_1 \space t_1 $$ $$ s_2 \space t_3 $$ $$ : $$ $$ s_M \space t_M $$ - 第一行为两个整数 $N(1 \leq N \leq 300,000)$ 和 $M(1 \leq M \leq 100,000)$ ，分别表示学校的教室数和学生数。 - 接下来的 $M$ 行，分别给出 $M$ 个扫除区间。这其中的第 $i(1 \leq i \leq M)$ 行给出表示第 $i$ 个扫除区间的整数 $s_i,t_i(1 \leq s_i \leq t_i \leq N)$ 。这表示某个学生需要打扫从 $s_i$ 到 $t_i$ 的所有教室。 - 可能有多个完全相同的区间。 - 任意教室至少被一个扫除区间包含。

第一行：输出即使翘掉扫除也不会暴露的扫除区间个数 $k$ 。 接下来 $k$ 行，输出这些区间的编号（升序排列）。最后一行的末尾需换行。 ## 部分分 对于 $30\%$ 的数据： - 对于任意的教室 $i(1 \leq i \leq N)$ ，包含这个教室的扫除区间的个数最大为 $2$ 。 ## 样例1解释 当高桥君负责第 $2,5$ 个扫除区间时不会暴露。具体来说： - 当高桥君负责第 $2$ 个扫除区间时，第 $5$ 个扫除区间包含了教室 $5$ 所以不会暴露。 - 当高桥君负责第 $5$ 个扫除区间时，第 $2$ 个扫除区间包含了教室 $5$ ，且第 $3$ 个扫除区间包含了教室 $6$ ，所以不会暴露。 然而，当高桥君负责第 $1,3,4$ 个扫除区间时，会暴露。具体来说： - 当高桥君负责第 $1$ 个扫除区间时，教室 $1,2,3,4$ 没有被扫除，故暴露了。 - 当高桥君负责第 $3$ 个扫除区间时，教室 $7,8$ 没有被扫除，故暴露了。 - 当高桥君负责第 $4$ 个扫除区间时，教室 $9,10$ 没有被扫除，故暴露了。 （个人认为第 $2,3$ 个样例解释是没有必要的）

### 部分点 上記の制約に加え，以下の制約を追加で満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 - 任意の教室 $ i\ (1≦i≦N) $ について，その教室を含む掃除区間の数は高々 $ 2 $ つである． ### Sample Explanation 1 高橋君が $ 2,5 $ 番目の掃除区間に割り当てられた場合には，サボってもバレない．具体的には， - $ 2 $ 番目の掃除区間を割り当てられても，$ 5 $ 番目の掃除区間が教室 $ 5 $ を含んでいるためバレない． - $ 5 $ 番目の掃除区間を割り当てられても，$ 2 $ 番目の掃除区間が教室 $ 5 $ を含んでおり，かつ $ 3 $ 番目の掃除区間が教室 $ 6 $ を含んでいるためバレない． 一方，高橋君が，$ 1,3,4 $ 番目の掃除区間に割り当てられた場合，サボるとバレる．具体的には， - $ 1 $ 番目の掃除区間を割り当てられた場合，教室 $ 1,2,3,4 $ が掃除されていないのでバレる． - $ 3 $ 番目の掃除区間を割り当てられた場合，教室 $ 7,8 $ が掃除されていないのでバレる． - $ 4 $ 番目の掃除区間を割り当てられた場合，教室 $ 9,10 $ が掃除されていないのでバレる． ### Sample Explanation 2 どんな掃除区間を選んでもサボることができる． ### Sample Explanation 3 高橋君がサボれる掃除区間が一つも無いということもありえる．