← 返回题目列表

Codeforces · 776/F

F. 夏洛克对莫里亚蒂的赌注

中文机器翻译题面 查看原题

夏洛克与莫里亚蒂进行了最后的斗智斗勇。他给了他一个正n边凸多边形。除此之外,他还给了他一定的对角线以在多边形上形成区域。保证对角线不在内点相交。

他选取了每个区域并计算了其重要性值。由多边形的顶点a1、a2、...、ax形成的区域的重要性值将由2a1+2a2+...+2ax给出。然后,他根据这些区域的重要性值按升序对这些区域进行排序。之后,他为每个区域分配了一个从 1 到 k 的索引,其中 k 是区域的数量,区域的索引是其在上面计算的排序数组中的位置。

他希望 Moriarty 使用不超过 20 种颜色对区域进行着色,这样,只有当两个区域之间的所有简单路径中至少有一个区域的颜色值小于分配给这些区域的颜色值时,两个区域才具有相同的颜色。两个区域 f 和 h 之间的简单路径是区域 r1, r2, ... rt 的序列,使得 r1 = f, rt = h,对于每个 1 ≤ i < t 区域 ri 和 ri + 1 共享一条边,并且当且仅当 i = j 时 ri = rj。

Moriarty无法回答并要求Sherlock自己解决。帮助夏洛克做到这一点。

输入

第一行包含两个整数 n 和 m (3 ≤ n ≤ 100000, 0 ≤ m ≤ n - 3)、多边形中的顶点数和添加的对角线数。

接下来的 m 行每行包含两个整数 a 和 b (1 ≤ a, b ≤ n),描述顶点 a 和 b 之间的对角线。保证对角线是正确的,即。 e. a 和 b 不重合且不相邻。保证对角线不相交。

输出

设区域数量为 k。

输出 k 个空格分隔的整数,每个整数在 1 到 20 之间,按重要性递增的顺序表示区域的颜色。

如果有多个答案,请打印其中任何一个。可以证明至少存在一个答案。

示例

输入 #1

4 1
1 3

输出 #1

1 2

输入 #2

6 3
1 3
1 4
1 5

输出 #2

2 1 2 3

注意

在第二个输入中,排序后按顺序形成的区域将为 (1, 2, 3)、(1, 3, 4)、(1, 4, 5)、(1, 5, 6),即区域 (1, 2, 3) 是第一个区域,然后是区域 (1, 3, 4),依此类推。

因此,我们可以用相同的颜色对区域 1 和 3 进行着色,因为区域号 2 位于从 1 到 3 的路径上,并且它的颜色 1 小于 1 和 3 的颜色,即颜色号 2。