Sherlock's bet to Moriarty
Contest: ICM Technex 2017 and Codeforces Round 400 (Div. 1 + Div. 2, combined)
Difficulty rating: 2800
Tags: constructive algorithms, data structures, divide and conquer, geometry, graphs, implementation, trees

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 a1, a2, ... , ax of the polygon will be given by 2a1 + 2a2 + ... + 2ax. 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 r1, r2, ... rt such that r1 = f, rt = h, for each 1 ≤ i < t regions ri and ri + 1 share an edge, and ri = rj if and only if i = j.

Moriarty couldn't answer and asks Sherlock to solve it himself. Help Sherlock in doing so.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

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

Example input:
4 1
1 3

Example output:
1 2

Example input:
6 3
1 3
1 4
1 5

Example output:
2 1 2 3

Editorial:
Hint: Observe that if we consider all regions as nodes for a graph and connect two regions if they share an edge (in the form of sharing a diagonal), we will get a tree.
Editorial: Use a greedy approach to form a tree from the given polygon. Let us take one diagonal between vertex a and b (b > a). Let us define a value x as minimum of two values b - a - 1 and n - 2 - (b - a - 1). Sort all the diagonals on the basis of this value x. This value is the minimum number of nodes between a and b. Remove the diagonals one by one. We can see that a new region will be formed each time which cannot be divided further, and this region will be formed on the side from where we got the value of x. Thus we can get the nodes in each region and form a tree. Then, this problem reduces to coloring the tree such that two regions have same color only if atleast one node between the two nodes with same color has a color with lesser value. This can be done by using the divide and conquer technique of centroid decomposition. Give each height in centroid tree a different color in increasing order.
Complexity: O(n * log(n))