CF739A Alyona and mex

Alyona 的妈妈想送给 Alyona 一个由 $n$ 个非负整数组成的数组，这个数组需要是特殊的。 Alyona 是个挑剔的女孩，所以收到数组后，她会检查 $m$ 个子数组。子数组是一组连续的数组元素。第 $i$ 个子数组由两个整数 $l_i$ 和 $r_i$ 描述，其元素为 $a[l_i], a[l_i+1], \ldots, a[r_i]$。 Alyona 会对她选中的每个子数组求出 mex。对于这 $m$ 个 mex，Alyona 会找出其中最小的一个。她希望这个最小的 mex 尽量大。 你需要构造一个长度为 $n$ 的数组 $a$，使得 Alyona 所选子数组中的最小 mex 尽可能大。 集合 $S$ 的 mex 是不在 $S$ 中的最小非负整数。

第一行包含两个整数 $n$ 和 $m$（$1\leq n, m\leq 10^5$）。 接下来的 $m$ 行，每行为 Alyona 选择的一个子数组的信息。第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1\leq l_i\leq r_i\leq n$），表示子数组 $a[l_i], a[l_i+1],\ldots,a[r_i]$。

第一行输出一个整数，表示这些子数组中最小的 mex 的最大值。 第二行输出 $n$ 个整数，表示数组 $a$。$a$ 中所有元素都应在 $0$ 到 $10^9$ 之间。 保证最优解中 $a$ 的所有元素都在 $0$ 到 $10^9$ 之间。 如果有多组解，输出任意一组均可。

第一个样例：子数组 $(1,3)$ 的 mex 等于 $3$，子数组 $(2,5)$ 的 mex 也等于 $3$，子数组 $(4,5)$ 的 mex 等于 $2$，因此 Alyona 选择的子数组中的最小 mex 等于 $2$。 由 ChatGPT 5 翻译