B - ドキドキデート大作戦高橋君 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君の通っている学校で大掃除が行われることになりました．学校には 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 行に，サボってもバレない掃除区間の番号を昇順に改行区切りで出力せよ．最後の行の末尾にも改行を入れること．

部分点

上記の制約に加え，以下の制約を追加で満たすデータセットに正解した場合は 30 点が与えられる。

  • 任意の教室 i (1≦i≦N) について，その教室を含む掃除区間の数は高々 2 つである．

入力例1

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

出力例1

2
2
5

高橋君が 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 6
1 1
1 1
2 2
2 2
3 3
3 3

出力例2

6
1
2
3
4
5
6

どんな掃除区間を選んでもサボることができる．

入力例3

10 3
1 4
2 6
6 10

出力例3

0

高橋君がサボれる掃除区間が一つも無いということもありえる．