問題
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