English · Original
Chinese · Translation
Formal · Original
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_.
## Input
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_\].
## Output
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.
[samples]
## Note
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.
Alyona 的母亲想送给 Alyona 一个包含 #cf_span[n] 个非负整数的数组。这个数组应该是特殊的。
Alyona 是个喜怒无常的女孩，因此在收到数组后，她会检查其中的 #cf_span[m] 个子数组。子数组是数组中若干连续元素的集合。第 #cf_span[i] 个子数组由两个整数 #cf_span[li] 和 #cf_span[ri] 描述，其元素为 #cf_span[a[li], a[li + 1], ..., a[ri]]。
Alyona 将为每个选定的子数组计算 _mex_。在这些 #cf_span[m] 个 _mex_ 中，她会找出最小的那个。她希望这个最小的 _mex_ 尽可能大。
你需要构造一个包含 #cf_span[n] 个元素的数组 #cf_span[a]，使得 Alyona 所选子数组中最小的 _mex_ 尽可能大。
集合 #cf_span[S] 的 _mex_ 是不在 #cf_span[S] 中的最小非负整数。
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 10^5]）。
接下来的 #cf_span[m] 行描述 Alyona 选择的子数组。第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ n]），描述子数组 #cf_span[a[li], a[li + 1], ..., a[ri]]。
第一行输出一个整数 —— 最大可能的最小 _mex_。
第二行输出 #cf_span[n] 个整数 —— 数组 #cf_span[a]。数组 #cf_span[a] 中的所有元素应在 #cf_span[0] 到 #cf_span[10^9] 之间。
保证存在一个最优解，其中所有元素都在 #cf_span[0] 到 #cf_span[10^9] 之间。
如果有多个解，输出任意一个即可。
第一个示例：子数组 #cf_span[(1, 3)] 的 _mex_ 为 #cf_span[3]，子数组 #cf_span[(2, 5)] 的 _mex_ 为 #cf_span[3]，子数组 #cf_span[(4, 5)] 的 _mex_ 也为 #cf_span[2]，因此 Alyona 选择的子数组中最小的 _mex_ 为 #cf_span[2]。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 10^5]）。接下来的 #cf_span[m] 行描述 Alyona 选择的子数组。第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ n]），描述子数组 #cf_span[a[li], a[li + 1], ..., a[ri]]。
## Output
第一行输出一个整数 —— 最大可能的最小 _mex_。第二行输出 #cf_span[n] 个整数 —— 数组 #cf_span[a]。数组 #cf_span[a] 中的所有元素应在 #cf_span[0] 到 #cf_span[10^9] 之间。保证存在一个最优解，其中所有元素都在 #cf_span[0] 到 #cf_span[10^9] 之间。如果有多个解，输出任意一个即可。
[samples]
## Note
第一个示例：子数组 #cf_span[(1, 3)] 的 _mex_ 为 #cf_span[3]，子数组 #cf_span[(2, 5)] 的 _mex_ 为 #cf_span[3]，子数组 #cf_span[(4, 5)] 的 _mex_ 也为 #cf_span[2]，因此 Alyona 选择的子数组中最小的 _mex_ 为 #cf_span[2]。
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \leq n, m \leq 10^5 $.
Let $ \mathcal{I} = \{ (l_i, r_i) \mid i \in \{1, \dots, m\} \} $ be a set of $ m $ subarray intervals, where $ 1 \leq l_i \leq r_i \leq n $.
Let $ a = (a_1, a_2, \dots, a_n) \in \mathbb{Z}_{\geq 0}^n $ be an array of non-negative integers.
For a subarray $ a[l_i:r_i] = \{a_{l_i}, a_{l_i+1}, \dots, a_{r_i}\} $, define its **mex** as:
$$
\text{mex}(a[l_i:r_i]) = \min \left( \mathbb{Z}_{\geq 0} \setminus \{a_j \mid l_i \leq j \leq r_i\} \right)
$$
Let $ M(a) = \min_{i=1}^m \text{mex}(a[l_i:r_i]) $ be the minimum mex over all chosen subarrays.
**Objective**
Maximize $ M(a) $ over all possible arrays $ a \in \mathbb{Z}_{\geq 0}^n $, i.e., find:
$$
\max_{a \in \mathbb{Z}_{\geq 0}^n} \min_{i=1}^m \text{mex}(a[l_i:r_i])
$$
**Constraints**
- All elements $ a_j \in [0, 10^9] $.
- The array $ a $ must be constructed such that the above objective is achieved.
API Response (JSON)
{
"problem": {
"name": "C. Alyona and mex",
"description": {
"content": "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 subarra",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF740C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Alyona's mother wants to present an array of _n_ non-negative integers to Alyona. The array should be special.\n\nAlyona is a capricious girl so after she gets the array, she inspects _m_ of its subarra...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Alyona 的母亲想送给 Alyona 一个包含 #cf_span[n] 个非负整数的数组。这个数组应该是特殊的。\n\nAlyona 是个喜怒无常的女孩，因此在收到数组后，她会检查其中的 #cf_span[m] 个子数组。子数组是数组中若干连续元素的集合。第 #cf_span[i] 个子数组由两个整数 #cf_span[li] 和 #cf_span[ri] 描述，其元素为 #cf_span[a[l...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m \\leq 10^5 $. \nLet $ \\mathcal{I} = \\{ (l_i, r_i) \\mid i \\in \\{1, \\dots, m\\} \\} $ be a set of $ m $ subarray intervals, where $ 1 \\leq...",
"is_translate": false,
"language": "Formal"
}
]
}