← 返回题目列表

AtCoder · arc190_a

A. 内部或外部

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

有一个整数序列 x = (x_1, \ldots, x_N),初始化为 x_1 = \cdots = x_N = 0.

您将执行 M 对此整数序列进行操作。在 i-th 操作,给你一个整数对 (L_i, R_i) 这样 1 \leq L_i \leq R_i \leq N,并且您必须执行 正好一个 以下三个操作:

  • 操作 0:什么都不做。此操作的成本为 0.
  • 操作 1:对于每个整数 j 与 1 \leq j \leq N,如果 L_i \leq j \leq R_i 成立,设置 x_j = 1。此操作的成本为 1.
  • 操作 2:对于每个整数 j 与 1 \leq j \leq N,如果 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 是运营的最小总成本,并且 \mathrm{op}_i 是操作类型(0, 1,或 2) 选择为 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).
  • 在第一次操作中,操作 执行 2 。 x_1 和 x_5 变为 1,所以 x = (1,0,0,0,1).
  • 在第二次操作中,操作 0 。 x 仍然存在 (1,0,0,0,1).
  • 在第三次操作中,操作 1 。 x_1, x_2, x_3, x_4 变为 1,所以 x = (1,1,1,1,1).
  • 在第四次操作中,操作 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