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