CF776F Sherlock's bet to Moriarty

夏洛克和莫里亚蒂进行了一场智慧的终极对决。他给莫里亚蒂一个正 $n$ 边凸多边形。此外，他又给了多边形若干条对角线，在多边形内部划分出了若干个区域。保证所有对角线在内部不会相交。 他对每一个区域计算其重要性值。某个由多边形上的顶点 $a_{1},a_{2},...\ ,a_{x}$ 构成的区域，其重要性值定义为 $2^{a_{1}}+2^{a_{2}}+\ldots+2^{a_{x}}$。接着，他将所有区域按照重要性值升序排序。然后按照排序后的顺序，从 $1$ 到 $k$（$k$ 为区域数）赋予索引。 现在他希望莫里亚蒂用不超过 $20$ 种颜色对这些区域染色。仅当下面条件成立时，两个区域可以染成同一种颜色：对于任意简单路径（即在区域之间按照共边走动，不能重复经过区域）连接这两个区域，路径上都至少有一个区域的颜色编号小于它们的颜色编号。具体地，设 $f$ 和 $h$ 是两个区域，简单路径表示为 $r_1, r_2, \ldots, r_t$，其中 $r_1=f, r_t=h$，且对于每个 $1 \leq i < t$，$r_i$ 与 $r_{i+1}$ 共享一条边，且 $r_i=r_j$ 仅当 $i=j$。只有当上述条件满足，两个区域才能染同色。 莫里亚蒂答不出来，于是他请夏洛克帮忙。请你帮助夏洛克解决该问题。

第一行包含两个整数 $n$ 和 $m$（$3 \leq n \leq 100000$，$0 \leq m \leq n-3$），分别表示多边形的顶点数以及添加的对角线数。 接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$（$1 \leq a,b \leq n$），表示一条连接顶点 $a$ 和 $b$ 的对角线。保证给出的所有对角线均合法，即 $a$ 和 $b$ 不重合且不是相邻顶点，并且所有对角线两两不在内部相交。

假设区域数为 $k$。 输出 $k$ 个用空格分隔的整数，每个整数为 $1$ 到 $20$ 之间，表示将区域按重要性值递增顺序排列后的染色编号。 如果有多种合法方案，输出任意一种均可。保证至少存在一种合法染色解。

对于第二组样例输入，区域按排序后依次为 $(1,2,3)$、$(1,3,4)$、$(1,4,5)$、$(1,5,6)$，即 $(1,2,3)$ 为第一个区域，接着是 $(1,3,4)$，以此类推。 因此，可以将区域 $1$ 和区域 $3$ 染成相同的颜色，因为区域 $2$ 位于从 $1$ 到 $3$ 的路径上，且其颜色编号比 $1$ 和 $3$ 更小（即编号为 $2$）。 由 ChatGPT 5 翻译