{"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 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_\\].\n\nAlyona 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.\n\nYou 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.\n\nThe _mex_ of a set _S_ is a minimum possible non-negative integer that is not in _S_.\n\n## Input\n\nThe first line contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 105).\n\nThe 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\n## Output\n\nIn the first line print single integer — the maximum possible minimum _mex_.\n\nIn the second line print _n_ integers — the array _a_. All the elements in _a_ should be between 0 and 109.\n\nIt is guaranteed that there is an optimal answer in which all the elements in _a_ are between 0 and 109.\n\nIf there are multiple solutions, print any of them.\n\n[samples]\n\n## Note\n\nThe 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.","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[li], a[li + 1], ..., a[ri]]。\n\nAlyona 将为每个选定的子数组计算 _mex_。在这些 #cf_span[m] 个 _mex_ 中，她会找出最小的那个。她希望这个最小的 _mex_ 尽可能大。\n\n你需要构造一个包含 #cf_span[n] 个元素的数组 #cf_span[a]，使得 Alyona 所选子数组中最小的 _mex_ 尽可能大。\n\n集合 #cf_span[S] 的 _mex_ 是不在 #cf_span[S] 中的最小非负整数。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 10^5]）。\n\n接下来的 #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]]。\n\n第一行输出一个整数 —— 最大可能的最小 _mex_。\n\n第二行输出 #cf_span[n] 个整数 —— 数组 #cf_span[a]。数组 #cf_span[a] 中的所有元素应在 #cf_span[0] 到 #cf_span[10^9] 之间。\n\n保证存在一个最优解，其中所有元素都在 #cf_span[0] 到 #cf_span[10^9] 之间。\n\n如果有多个解，输出任意一个即可。\n\n第一个示例：子数组 #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]。\n\n## Input\n\n第一行包含两个整数 #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]]。\n\n## Output\n\n第一行输出一个整数 —— 最大可能的最小 _mex_。第二行输出 #cf_span[n] 个整数 —— 数组 #cf_span[a]。数组 #cf_span[a] 中的所有元素应在 #cf_span[0] 到 #cf_span[10^9] 之间。保证存在一个最优解，其中所有元素都在 #cf_span[0] 到 #cf_span[10^9] 之间。如果有多个解，输出任意一个即可。\n\n[samples]\n\n## Note\n\n第一个示例：子数组 #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]。","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 l_i \\leq r_i \\leq n $.  \nLet $ a = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}_{\\geq 0}^n $ be an array of non-negative integers.  \n\nFor a subarray $ a[l_i:r_i] = \\{a_{l_i}, a_{l_i+1}, \\dots, a_{r_i}\\} $, define its **mex** as:  \n$$\n\\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)\n$$\n\nLet $ M(a) = \\min_{i=1}^m \\text{mex}(a[l_i:r_i]) $ be the minimum mex over all chosen subarrays.\n\n**Objective**  \nMaximize $ M(a) $ over all possible arrays $ a \\in \\mathbb{Z}_{\\geq 0}^n $, i.e., find:  \n$$\n\\max_{a \\in \\mathbb{Z}_{\\geq 0}^n} \\min_{i=1}^m \\text{mex}(a[l_i:r_i])\n$$\n\n**Constraints**  \n- All elements $ a_j \\in [0, 10^9] $.  \n- The array $ a $ must be constructed such that the above objective is achieved.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF740C","tags":["constructive algorithms"],"sample_group":[["5 3\n1 3\n2 5\n4 5","2\n1 0 2 1 0"],["4 2\n1 4\n2 4","3\n5 2 0 1"]],"created_at":"2026-03-03 11:00:39"}}