AT_arc190_a.[ARC190A] Inside or Outside

有一个整数序列 $x = (x_1, \ldots, x_N)$，初始时 $x_1 = \cdots = x_N = 0$。

你需要对这个整数序列进行 $M$ 次操作。第 $i$ 次操作会给出一组整数 $(L_i, R_i)$，满足 $1 \leq L_i \leq R_i \leq N$，你需要从以下 $3$ 种操作中恰好选择一种进行：

• 操作 $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$ 成立。请判断该目标是否可以达成。如果可以达成，请在所有可行方案中，输出总代价最小的一种。

输入按以下格式从标准输入读入：

$N$ $M$
$L_1$ $R_1$
$\vdots$
$L_M$ $R_M$

如果目标无法达成，输出 -1。

如果目标可以达成，则输出总代价的最小值 $K$，以及每次操作选择的操作类型（$0$ 或 $1$ 或 $2$），格式如下：

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

如果有多种总代价最小的方案，输出任意一种均可。

限制

• $1 \leq N \leq 1000000$
• $1 \leq M \leq 200000$
• $1 \leq L_i \leq R_i \leq N$
• 所有输入的值均为整数

样例解释 1

输出样例中 $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)$。

由 ChatGPT 4.1 翻译