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 翻译