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。