A - Inside or Outside Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

整数列 x = (x_1, \ldots, x_N) があり，x_1=\cdots=x_N=0 で初期化されています．

あなたはこの整数列について，M 回の操作を行います．i 回目の操作では，1\leq L_i\leq R_i\leq N を満たす整数の組 (L_i, R_i) が与えられるので，以下の 3 つのうちちょうど 1 つを行います．

  • 操作 0：何もしない．この操作にはコストが 0 かかる．
  • 操作 1：1\leq j\leq N を満たす各整数 j に対して，L_i\leq j\leq R_i を満たすならば x_j=1 と定める．この操作にはコストが 1 かかる．
  • 操作 2：1\leq j\leq N を満たす各整数 j に対して，L_i\leq j\leq R_i を満たさないならば x_j=1 と定める．この操作にはコストが 1 かかる．

あなたの目標は，最終的に x_1=\cdots=x_N=1 が成り立つようにすることです．この目標が達成できるか否かを判定してください．目標が達成可能な場合には，そのような方法のうち操作にかかるコストの総和が最小となるものをひとつ答えてください．

制約

  • 1\leq N\leq 1000000
  • 1\leq M\leq 200000
  • 1\leq L_i\leq R_i\leq N
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられます．

N M
L_1 R_1
\vdots
L_M R_M

出力

目標が達成不可能な場合には -1 と出力してください．

目標が達成可能な場合には，そのような方法のうち操作にかかるコストの総和が最小となるものを，コストの総和の最小値を K，i 回目で行う操作の種類（0 または 1 または 2）を \mathrm{op}_i として，次の形式で出力してください．

K
\mathrm{op}_1 \cdots \mathrm{op}_M

操作にかかるコストの総和を最小化する方法が複数存在する場合には，そのどれを出力しても正解となります．

入力例 1

5 4
2 4
3 5
1 4
2 5

出力例 1

2
2 0 1 0

出力例では x は次のように変化します．

  • はじめ x=(0,0,0,0,0) である．
  • 1 回目の操作で操作 2 を行う．x_1,x_5 が 1 になり，x=(1,0,0,0,1) になる．
  • 2 回目の操作で操作 0 を行う．x=(1,0,0,0,1) になる．
  • 3 回目の操作で操作 1 を行う．x_1,x_2,x_3,x_4 が 1 になり，x=(1,1,1,1,1) になる．
  • 4 回目の操作で操作 0 を行う．x=(1,1,1,1,1) になる．

入力例 2

5 4
1 3
1 5
2 4
3 5

出力例 2

1
0 1 0 0

入力例 3

5 2
1 3
2 5

出力例 3

2
1 1

入力例 4

5 2
1 3
2 4

出力例 4

-1

Score : 700 points

Problem Statement

There is an integer sequence x = (x_1, \ldots, x_N), which is initialized with x_1 = \cdots = x_N = 0.

You will perform M operations on this integer sequence. In the i-th operation, you are given an integer pair (L_i, R_i) such that 1 \leq L_i \leq R_i \leq N, and you must perform exactly one of the following three operations:

  • Operation 0: Do nothing. This operation incurs a cost of 0.
  • Operation 1: For each integer j with 1 \leq j \leq N, if L_i \leq j \leq R_i holds, set x_j = 1. This operation incurs a cost of 1.
  • Operation 2: For each integer j with 1 \leq j \leq N, if L_i \leq j \leq R_i does not hold, set x_j = 1. This operation incurs a cost of 1.

Your goal is to make x_1 = \cdots = x_N = 1 hold at the end. Determine whether this goal can be achieved. If it can be achieved, present one way to achieve it where the total cost of the operations is minimized.

Constraints

  • 1 \leq N \leq 1000000
  • 1 \leq M \leq 200000
  • 1 \leq L_i \leq R_i \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
L_1 R_1
\vdots
L_M R_M

Output

If the goal is not achievable, print -1.

If the goal is achievable, print one way to achieve it where the total cost of the operations is minimized, in the following format, where K is the minimum total cost of the operations, and \mathrm{op}_i is the type of operation (0, 1, or 2) chosen for the i-th operation.

K
\mathrm{op}_1 \cdots \mathrm{op}_M

If there are multiple ways that minimize the total cost, printing any one of them is accepted.

Sample Input 1

5 4
2 4
3 5
1 4
2 5

Sample Output 1

2
2 0 1 0

In the sample output, x changes as follows:

  • Initially, x = (0,0,0,0,0).
  • In the 1st operation, Operation 2 is performed. x_1 and x_5 become 1, so x = (1,0,0,0,1).
  • In the 2nd operation, Operation 0 is performed. x remains (1,0,0,0,1).
  • In the 3rd operation, Operation 1 is performed. x_1, x_2, x_3, x_4 become 1, so x = (1,1,1,1,1).
  • In the 4th operation, Operation 0 is performed. x remains (1,1,1,1,1).

Sample Input 2

5 4
1 3
1 5
2 4
3 5

Sample Output 2

1
0 1 0 0

Sample Input 3

5 2
1 3
2 5

Sample Output 3

2
1 1

Sample Input 4

5 2
1 3
2 4

Sample Output 4

-1