CF739A.Alyona and mex

Alyona's mother wants to present an array of n non-negative integers to Alyona. The array should be special.

Alyona is a capricious girl so after she gets the array, she inspects m of its subarrays. Subarray is a set of some subsequent elements of the array. The i-th subarray is described with two integers l__i and r__i, and its elements are a[l__i], a[l__i + 1], ..., a[r__i].

Alyona is going to find mex for each of the chosen subarrays. Among these m mexes the girl is going to find the smallest. She wants this minimum mex to be as large as possible.

You are to find an array a of n elements so that the minimum mex among those chosen by Alyona subarrays is as large as possible.

The mex of a set S is a minimum possible non-negative integer that is not in S.

Alyona 的母亲想送给她一个由 $n$ 个非负整数组成的数组。该数组需满足“特殊”要求。

Alyona 是一位任性的女孩，因此在收到数组后，她会检查其中的 $m$ 个子数组。子数组是指原数组中若干连续元素组成的集合。第 $i$ 个子数组由两个整数 $l_i$ 和 $r_i$ 描述，其元素为 $a[l_i],\ a[l_i + 1],\ \dots,\ a[r_i]$。

Alyona 将对每个选定的子数组计算其 mex 值。然后，她将在这些 $m$ 个 mex 值中找出最小值。她希望这个最小 mex 尽可能大。

你需要构造一个长度为 $n$ 的数组 $a$，使得 Alyona 所选的 $m$ 个子数组对应的 mex 值中的最小值尽可能大。

集合 $S$ 的 mex 定义为：不在 $S$ 中的最小非负整数。

The first line contains two integers n and m (1 ≤ n, m ≤ 105).

The next m lines contain information about the subarrays chosen by Alyona. The i-th of these lines contains two integers l__i and r__i (1 ≤ l__i ≤ r__i ≤ n), that describe the subarray a[l__i], a[l__i + 1], ..., a[r__i].

第一行包含两个整数 $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],\ \dots,\ a[r_i]$。

In the first line print single integer — the maximum possible minimum mex.

In the second line print n integers — the array a. All the elements in a should be between 0 and 109.

It is guaranteed that there is an optimal answer in which all the elements in a are between 0 and 109.

If there are multiple solutions, print any of them.

第一行输出一个整数——可能的最大最小 mex 值。

第二行输出 $n$ 个整数——数组 $a$。$a$ 中所有元素均应在 $0$ 到 $10^9$ 之间。

保证存在一个最优解，其中 $a$ 的所有元素均在 $0$ 到 $10^9$ 之间。

若存在多个解，输出任意一个即可。

The first example: the mex of the subarray (1, 3) is equal to 3, the mex of the subarray (2, 5) is equal to 3, the mex of the subarray (4, 5) is equal to 2 as well, thus the minumal mex among the subarrays chosen by Alyona is equal to 2.

第一个例子：子数组 $(1,\,3)$ 的 mex 等于 $3$，子数组 $(2,\,5)$ 的 mex 等于 $3$，子数组 $(4,\,5)$ 的 mex 也等于 $2$，因此 Alyona 所选子数组中最小的 mex 值为 $2$。