Alyona and mex

题意翻译

你有 $m$ 个区间，要求构造一个长度为 $n$ 的序列使得这 $m$ 个区间中 $\text{mex}$ 最小的最大（$\text{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 $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1<=n,m<=10^{5} $ ). 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}] $ .

输出格式

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 $ 10^{9} $ . It is guaranteed that there is an optimal answer in which all the elements in $ a $ are between $ 0 $ and $ 10^{9} $ . If there are multiple solutions, print any of them.

输入输出样例

输入样例 #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

说明

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 $ .