Sherlock's bet to Moriarty

题意翻译

存在一个 $n$ 个点的多边形，点按顺序从 $1$ 到 $n$ 标号。$m$ 条不在除了端点以外的地方相交的对角线将多边形划分成 $m + 1$ 个区域 $R_1, R_2, \cdots, R_{m + 1}$。 令某个区域的端点为 $a_1, a_2, \cdots, a_{|R_i|}$，定义一个区域的重要度为 $f(R_i) = \sum\limits_{j = 1} ^ {|R_i|} 2 ^ {a_j}$。将所有区域按重要度从小到大排序并编号，即 $f(R_1) < f(R_2) < \cdots < f(R_{m + 1})$。 现在，你要给每个区域染上一种颜色，用一个 $1\sim 20$ 之间的正整数表示。 求出这样一种染色方案，使得对于任意两个颜色相同的区域 $R_i$ 和 $R_j(i\neq j)$，均满足它们之间的任何一条简单路径上都均存在至少一个区域 $R_k$ 使得 $R_k$ 的颜色小于 $R_i$ 和 $R_j$​ 的颜色。简单路径定义为不经过重复区域，且路径上相邻两个区域有一条公共边的路径。 按编号顺序输出每个区域的颜色。 可以证明在题目限制下一定存在解，若有多解输出任意一个。 $3\leq n \leq 10 ^ 5$，$0\leq m \leq n - 3$。

题目描述

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. He 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. He 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&lt;t $ regions $ r_{i} $ and $ r_{i+1} $ share an edge, and $ r_{i}=r_{j} $ if and only if $ i=j $ . Moriarty couldn't answer and asks Sherlock to solve it himself. Help Sherlock in doing so.

输入输出格式

输入格式

First 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. Each 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.

输出格式

Let the number of regions be $ k $ . Output $ k $ space-separated integers, each between $ 1 $ and $ 20 $ , representing the colors of the regions in the order of increasing importance. If there are multiple answers, print any of them. It can be shown that at least one answer exists.

输入输出样例

输入样例 #1

4 1
1 3

输出样例 #1

1 2

输入样例 #2

6 3
1 3
1 4
1 5

输出样例 #2

2 1 2 3

说明

In 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. So, 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 $ .