005 - スイッチ

時間制限 1 秒 / メモリ制限 256 MB / 得点 250 / x 1 /

TLE
1sec
MLE
256MB
得点
250

問題

ON と OFF の状態をもつ W 個のスイッチが横に並んでいます。 左から 1, 2, ..., W の番号が振られています。

最初, 全てのスイッチは OFF です。 スイッチは 1 回押すごとに, そのスイッチの状態が反転されます。 具体的にはスイッチが OFF のとき押されると ON, ON のときに押されると OFF になります。

Q 匹のうさぎちゃんがいます。 1 番目のうさぎちゃんから順に, 並べられたスイッチに対し以下の操作をしました。

  • スイッチ Li からスイッチ Ri の区間(両端を含む)にあるすべてのスイッチを 1 回ずつ押す。

ここですべてのスイッチを ON にしたくなったので, 上の操作を自分でもう何回か行うことにしました。 操作する区間は各操作で好きなように選ぶことが出来ます。 適切に区間を選んだ時, すべてのスイッチを ON にするための最小操作回数を求め, その手順を出力してください。

入力

W Q
L1 R1
L2 R2
:
LQ RQ

1 行目には, スイッチの個数 W(1 ≤ W ≤ 200 000) とうさぎちゃんの匹数 Q(0 ≤ Q ≤ 200 000) が与えられます。

つづく Q 行にかけて操作の情報が与えられます。このうち i 行目は i 番目のうさぎちゃんがスイッチ Li からスイッチ Ri(1 ≤ Li < Ri ≤ W) の区間を押すことを表します。

出力

K
L1 R1
L2 R2
:
LK RK

1 行目にすべてのスイッチを ON にするための最小操作回数 K を出力してください。 既に全てのスイッチが ON のときは 0 を出力してください。
2 行目から K 行にかけて, 操作する区間 Li と Ri(1 ≤ Li ≤ Ri ≤ W) を半角空白区切りで 1 行ずつ出力してください。

解が複数ある場合が考えられますが, 条件を満たせばどのように出力しても構いません。

部分点

採点データのうちの 30 ％は W ≤ 1000, Q ≤ 1000 を追加で満たします。

入出力例

入力例 1

5 2
1 4
3 5

出力例 1

1
3 4
  • Q 匹のうさぎちゃんの操作後のスイッチの状態は左から 11001 です。
  • スイッチ 3 からスイッチ 4 の区間を反転すれば, 1 回の操作ですべてのスイッチを ON にすることができます。

入力例 2

5 3
2 4
1 5
3 3

出力例 2

2
3 3
2 4
  • Q 匹のうさぎちゃんの操作後のスイッチの状態は左から 10101 です。
  • 最小の操作回数は 2 です。例えば, スイッチ 3 を押して, 次にスイッチ 2 から 4 の範囲を押すことで達成できます。

入力例 3

5 4
2 5
1 5
1 1
1 5

出力例 3

0