← 返回题目列表

Codeforces · 739/A

A. 阿廖娜和墨西哥

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

Alyona 的母亲想要向 Alyona 呈现一个包含 n 个非负整数的数组。该数组应该是特殊的。

Alyona 是一个反复无常的女孩,所以在她拿到数组后,她检查了 m 个子数组。子数组是数组中一些后续元素的集合。第i个子数组用两个整数li和ri描述,其元素为a[li],a[li + 1],...,a[ri]。

Alyona 将为每个选定的子数组找到 mex。在这些米克斯中,女孩要找到最小的。她希望这个最小的墨西哥人尽可能大。

您需要找到一个包含 n 个元素的数组 a,使得 Alyona 子数组选择的最小 mex 尽可能大。

集合 S 的 mex 是不在 S 中的最小可能非负整数。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 105)。

接下来的 m 行包含有关 Alyona 选择的子阵列的信息。这些行的第 i 行包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ n),它们描述子数组 a[li], a[li + 1], ..., a[ri]。

输出

在第一行中打印单个整数 - 最大可能的最小 mex。

在第二行中打印 n 个整数——数组 a。 a 中的所有元素都应在 0 到 109 之间。

保证存在一个最优答案,其中a中的所有元素都在0到109之间。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

5 3
1 3
2 5
4 5

输出 #1

2
1 0 2 1 0

输入 #2

4 2
1 4
2 4

输出 #2

3
5 2 0 1

注意

第一个例子:子数组(1, 3)的mex等于3,子数组(2, 5)的mex等于3,子数组(4, 5)的mex也等于2,因此Alyona选择的子数组中的最小mex等于2。