[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$ 个样例解释是没有必要的）

[problemUrl]: https://atcoder.jp/contests/arc045/tasks/arc045_b 高橋君の通っている学校で大掃除が行われることになりました．学校には $ N $ 個の教室があり，各教室は $ 1 $ から $ N $ まで順番に番号付けられており，左から右に並んでいます． 高橋君の学校には高橋君を含め $ M $ 人の生徒がおり，掃除すべき連続した教室の区間(掃除区間と呼ぶ)は $ M $ 個既に決まっています．しかし，それらの掃除区間を誰が担当するかは決まっていません． 異なる生徒には異なる掃除区間が割り当てられ，割り当てられた生徒はそれに含まれる全ての教室を掃除しなければなりません．$ 1 $ つの教室が複数の掃除区間に含まれることがあります． 高橋君は大掃除の日に女の子とのデートの約束をしていることに気づきました．デートをサボってしまうと何が起こるか分からないので大掃除をサボることに決めました． 前述の通りいくつかの教室については複数の掃除区間に含まれていることがあるので，高橋君の担当分をサボっても全ての教室を誰かが掃除してくれさえすれば，サボったことがバレないことに気づきました． 掃除されていない教室があった場合には，サボったことがバレます． あなたの仕事は高橋君のために，サボってもバレない掃除区間を全て教えてあげることです． なお，この学校の生徒は高橋君を除きみんな真面目なので，高橋君以外がサボることは無いと仮定してください．

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ s_1 $ $ t_1 $ $ s_2 $ $ t_2 $ : $ s_M $ $ t_M $ - $ 1 $ 行目には，学校の教室の数を表す整数 $ N\ (1\ ≦\ N\ ≦\ 300,000) $ と生徒の数を表す整数 $ M(1\ ≦\ M\ ≦\ 100,000) $ が与えられる． - 続く $ M $ 行には，$ M $ 個の掃除区間が与えられる．このうち $ i(1≦i≦M) $ 行目には，$ i $番目の掃除区間を表す整数 $ s_i,t_i(1≦s_i≦t_i≦N) $ が与えられる．これは，もしある生徒がその掃除区間を割り当てられた時，$ s_i≦x≦t_i $ を満たす全ての教室 $ x $ について掃除を行わなければならないことを表す． - 全く同じ区間が複数個与えられることもありえる． - 任意の教室は少なくとも $ 1 $ つの掃除区間に含まれることが保証される．

出力は標準出力に行うこと． $ 1 $ 行目に，サボってもバレない掃除区間の数 $ k $ を出力せよ． 続く $ k $ 行に，サボってもバレない掃除区間の番号を昇順に改行区切りで出力せよ．最後の行の末尾にも改行を入れること．

10 5
1 4
5 5
6 8
9 10
5 6

2
2
5

3 6
1 1
1 1
2 2
2 2
3 3
3 3

6
1
2
3
4
5
6

10 3
1 4
2 6
6 10

0

### 部分点 上記の制約に加え，以下の制約を追加で満たすデータセットに正解した場合は $ 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 高橋君がサボれる掃除区間が一つも無いということもありえる．