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.