{"problem":{"name":"F. Sherlock's bet to Moriarty","description":{"content":"Sherlock met Moriarty for a final battle of wits. He gave him a regular _n_ sided convex polygon. In addition to it, he gave him certain diagonals to form regions on the polygon. It was guaranteed tha","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF776F"},"statements":[{"statement_type":"Markdown","content":"Sherlock met Moriarty for a final battle of wits. He gave him a regular _n_ sided convex polygon. In addition to it, he gave him certain diagonals to form regions on the polygon. It was guaranteed that the diagonals did not intersect in interior points.\n\nHe took each of the region and calculated its importance value. Importance value for a region formed by vertices _a_1, _a_2, ... , _a__x_ of the polygon will be given by 2_a_1 + 2_a_2 + ... + 2_a__x_. Then, he sorted these regions on the basis of their importance value in ascending order. After that he assigned each region an index from 1 to _k_, where _k_ is the number of regions, and index of region is its position in the sorted array calculated above.\n\nHe wants Moriarty to color the regions using not more than 20 colors, such that two regions have same color only if all the simple paths between these two regions have at least one region with color value less than the color value assigned to these regions. Simple path between two regions _f_ and _h_ is a sequence of regions _r_1, _r_2, ... _r__t_ such that _r_1 = _f_, _r__t_ = _h_, for each 1 ≤ _i_ < _t_ regions _r__i_ and _r__i_ + 1 share an edge, and _r__i_ = _r__j_ if and only if _i_ = _j_.\n\nMoriarty couldn't answer and asks Sherlock to solve it himself. Help Sherlock in doing so.\n\n## Input\n\nFirst line contains two integers _n_ and _m_ (3 ≤ _n_ ≤ 100000, 0 ≤ _m_ ≤ _n_ - 3), the number of vertices in the polygon and the number of diagonals added.\n\nEach of the next _m_ lines contains two integers _a_ and _b_ (1 ≤ _a_, _b_ ≤ _n_), describing a diagonal between vertices _a_ and _b_. It is guaranteed that the diagonals are correct, i. e. _a_ and _b_ don't coincide and are not neighboring. It is guaranteed that the diagonals do not intersect.\n\n## Output\n\nLet the number of regions be _k_.\n\nOutput _k_ space-separated integers, each between 1 and 20, representing the colors of the regions in the order of increasing importance.\n\nIf there are multiple answers, print any of them. It can be shown that at least one answer exists.\n\n[samples]\n\n## Note\n\nIn 2nd input, regions formed in order after sorting will be (1, 2, 3), (1, 3, 4), (1, 4, 5), (1, 5, 6), i.e, region (1, 2, 3) is first region followed by region (1, 3, 4) and so on.\n\nSo, we can color regions 1 and 3 with same color, as region number 2 is on the path from 1 to 3 and it has color 1 which is less than color of 1 and 3, i.e., color number 2.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Sherlock 与 Moriarty 进行了一场智慧的最终对决。他给了 Moriarty 一个具有 #cf_span[n] 个顶点的正则凸多边形，并添加了一些对角线以将多边形划分为若干区域。保证这些对角线在内部不相交。\n\n他计算了每个区域的重要性值。由多边形顶点 #cf_span[a1, a2, ... , ax] 构成的区域的重要性值定义为 #cf_span[2a1 + 2a2 + ... + 2ax]。随后，他根据重要性值的升序对这些区域进行排序。之后，他将每个区域分配一个从 #cf_span[1] 到 #cf_span[k] 的索引，其中 #cf_span[k] 是区域的总数，索引即为该区域在上述排序数组中的位置。\n\n他希望 Moriarty 使用不超过 #cf_span[20] 种颜色为这些区域着色，使得两个区域具有相同颜色，当且仅当连接这两个区域的所有简单路径上，都至少存在一个区域，其颜色值小于这两个区域的颜色值。两个区域 #cf_span[f] 和 #cf_span[h] 之间的简单路径是一系列区域 #cf_span[r1, r2, ... rt]，满足 #cf_span[r1 = f]，#cf_span[rt = h]，对于每个 #cf_span[1 ≤ i < t]，区域 #cf_span[ri] 和 #cf_span[ri + 1] 共享一条边，且当且仅当 #cf_span[i = j] 时 #cf_span[ri = rj]。\n\nMoriarty 无法解答，于是请求 Sherlock 自行解决。请帮助 Sherlock 解决这个问题。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[3 ≤ n ≤ 100000]，#cf_span[0 ≤ m ≤ n - 3]），分别表示多边形的顶点数和添加的对角线数。\n\n接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ a, b ≤ n]），描述一条连接顶点 #cf_span[a] 和 #cf_span[b] 的对角线。保证对角线合法，即 #cf_span[a] 和 #cf_span[b] 不重合且不相邻。保证对角线互不相交。\n\n设区域总数为 #cf_span[k]。\n\n请输出 #cf_span[k] 个用空格分隔的整数，每个整数在 #cf_span[1] 到 #cf_span[20] 之间，表示按重要性升序排列的各区域的颜色。\n\n如果有多个答案，输出任意一个即可。可以证明至少存在一个有效答案。\n\n在第二个输入样例中，排序后形成的区域依次为 #cf_span[(1, 2, 3)]、#cf_span[(1, 3, 4)]、#cf_span[(1, 4, 5)]、#cf_span[(1, 5, 6)]，即区域 #cf_span[(1, 2, 3)] 为第一个区域，接着是区域 #cf_span[(1, 3, 4)]，依此类推。\n\n因此，我们可以将区域 #cf_span[1] 和 #cf_span[3] 染成相同颜色，因为从 #cf_span[1] 到 #cf_span[3] 的路径上经过区域 #cf_span[2]，而区域 #cf_span[2] 的颜色为 #cf_span[1]，小于区域 #cf_span[1] 和 #cf_span[3] 的颜色（即颜色编号 #cf_span[2]）。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[3 ≤ n ≤ 100000]，#cf_span[0 ≤ m ≤ n - 3]），分别表示多边形的顶点数和添加的对角线数。接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ a, b ≤ n]），描述一条连接顶点 #cf_span[a] 和 #cf_span[b] 的对角线。保证对角线合法，即 #cf_span[a] 和 #cf_span[b] 不重合且不相邻。保证对角线互不相交。\n\n## Output\n\n设区域总数为 #cf_span[k]。请输出 #cf_span[k] 个用空格分隔的整数，每个整数在 #cf_span[1] 到 #cf_span[20] 之间，表示按重要性升序排列的各区域的颜色。如果有多个答案，输出任意一个即可。可以证明至少存在一个有效答案。\n\n[samples]\n\n## Note\n\n在第二个输入样例中，排序后形成的区域依次为 #cf_span[(1, 2, 3)]、#cf_span[(1, 3, 4)]、#cf_span[(1, 4, 5)]、#cf_span[(1, 5, 6)]，即区域 #cf_span[(1, 2, 3)] 为第一个区域，接着是区域 #cf_span[(1, 3, 4)]，依此类推。因此，我们可以将区域 #cf_span[1] 和 #cf_span[3] 染成相同颜色，因为从 #cf_span[1] 到 #cf_span[3] 的路径上经过区域 #cf_span[2]，而区域 #cf_span[2] 的颜色为 #cf_span[1]，小于区域 #cf_span[1] 和 #cf_span[3] 的颜色（即颜色编号 #cf_span[2]）。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ P $ be a convex $ n $-gon with vertices labeled $ 1, 2, \\dots, n $ in cyclic order.  \nLet $ D $ be a set of $ m $ non-intersecting diagonals, partitioning $ P $ into $ k $ regions.  \nEach region $ R $ is a simple polygon defined by a cyclic sequence of vertices $ (v_1, v_2, \\dots, v_x) $, where $ x \\geq 3 $.  \n\n**Importance Value**  \nFor a region $ R = (v_1, v_2, \\dots, v_x) $, define its importance value as:  \n$$\n\\text{importance}(R) = \\sum_{i=1}^{x} 2^{v_i}\n$$\n\n**Region Ordering**  \nLet $ \\mathcal{R} = \\{R_1, R_2, \\dots, R_k\\} $ be the set of regions, sorted in ascending order of their importance values:  \n$$\n\\text{importance}(R_1) < \\text{importance}(R_2) < \\dots < \\text{importance}(R_k)\n$$  \nLet $ \\text{index}(R_i) = i $ denote the position of region $ R_i $ in this sorted list.\n\n**Dual Graph**  \nLet $ G = (V, E) $ be the dual graph of the polygon subdivision:  \n- Each region $ R_i $ corresponds to a vertex $ v_i \\in V $.  \n- An edge $ (v_i, v_j) \\in E $ exists iff regions $ R_i $ and $ R_j $ share a common edge (i.e., are adjacent).\n\n**Coloring Constraint**  \nAssign a color $ c(R_i) \\in \\{1, 2, \\dots, 20\\} $ to each region $ R_i $ such that:  \nFor any two regions $ R_i, R_j $ with $ c(R_i) = c(R_j) = c $, every simple path in $ G $ from $ v_i $ to $ v_j $ contains at least one region $ R_\\ell $ with $ c(R_\\ell) < c $.\n\n**Objective**  \nOutput $ c(R_1), c(R_2), \\dots, c(R_k) $ — the colors of the regions in order of increasing importance.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF776F","tags":["constructive algorithms","data structures","divide and conquer","geometry","graphs","implementation","trees"],"sample_group":[["4 1\n1 3","1 2"],["6 3\n1 3\n1 4\n1 5","2 1 2 3"]],"created_at":"2026-03-03 11:00:39"}}