CF776F.Sherlock's bet to Moriarty

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

夏洛克与莫里亚蒂展开了一场最终的智力对决。他给了莫里亚蒂一个正 $n$ 边形凸多边形。此外，他还给出了一些对角线，用以将该多边形划分为若干区域。题目保证这些对角线在多边形内部不相交。

他对每个区域计算其“重要性值”。若某区域由多边形的顶点 $a_1,\,a_2,\,\dots,\,a_x$ 构成，则其重要性值定义为 $2^{a_1} + 2^{a_2} + \dots + 2^{a_x}$。接着，他将所有区域按其重要性值升序排序。然后，他给每个区域分配一个从 $1$ 到 $k$ 的索引（其中 $k$ 是区域总数），该索引即为该区域在上述排序后数组中的位置。

他要求莫里亚蒂使用至多 $20$ 种颜色对这些区域进行着色，使得：仅当任意连接这两个区域的简单路径上均至少存在一个颜色值严格小于这两个区域颜色值的区域时，这两个区域才可被赋予相同颜色。
这里，区域 $f$ 与 $h$ 之间的简单路径定义为一个区域序列 $r_1,\,r_2,\,\dots,\,r_t$，满足：$r_1 = f$，$r_t = h$；对每个 $1 \le i < t$，区域 $r_i$ 与 $r_{i+1}$ 共享一条边；且对任意 $i,j$，有 $r_i = r_j$ 当且仅当 $i = j$。

莫里亚蒂无法解答，转而请求夏洛克自己解决这个问题。请帮助夏洛克完成这一任务。

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.

第一行包含两个整数 $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$ 不重合，且不相邻。同时保证所有对角线互不相交。

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.

设区域的数量为 $k$。

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

若存在多个答案，输出任意一个即可。可以证明至少存在一个答案。

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.

在第二个输入中，排序后依次形成的区域为 $(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）。