Baby Bob’s Coloring Book

Baby Bob celebrated his birthday recently, and just as you would expect, he received an extraordinary amount of presents from his family. His favorite gift is a coloring book, which contains colorless images that he can fill with colors however he wants to. Baby Bob’s absolute favorite images do not depict childish things like dogs and birds but rather display more abstract objects like triangles, circles, and so on.

Today, Baby Bob has discovered a nice image. The image contains $N$ empty circles arranged over the perimeter of a large circle. The circles are numbered from $0$ to $N − 1$ clockwise. There are line segments connecting circle $i$ and circle $i + 1$ for each $i = 0 . . . N − 2$, as well as circle $N − 1$ and circle $0$.
Baby Bob liked this picture and decided to modify it a bit. He drew $M$ additional straight line segments. These new segments satisfy the following criteria:

• Each new line segment connects two circles that were not connected before.
• No two line segments intersect each other.
• All circles connected by the new segments are distinct, i.e., each circle is connected to *at most one other circle by a new line.

Baby Bob wants to color the circles in his image. He only has crayons of two colors, red and blue. He wants to avoid coloring circles connected by line segments with the same color, but he is mature enough to accept that sometimes he cannot avoid doing so. Instead, he wants to color them such that the numbe of pairs of circles connected by a line segment and having the same color is minimal.

Help Baby Bob by writing a program that finds an optimal coloring of the circles.

Input data

The input file consists of:

• a line containing integers $N$ and $M$, the number of circles and the number of extra line segments, respectively.
• $M$ lines, the $i$-th of which consisting of integers $U_i$ and $V_i$, meaning that Baby Bob drew a line segment connecting circle $U_i$ and circle $V_i$.

Note that the original $N$ line segments are not included in the input.

Output data

The output file must contain two lines:

• a line containing a single integer $K$, the minimum number of connected pairs of circles that have the same color in an optimal coloring.
• a line consisting of the $N$ integers $C_0, . . . , C_{N−1}$, the description of an optimal coloring. $C_i$ is $0$ if circle $i$ should be colored red, and $1$, if it should be colored blue.

If there are multiple optimal colorings, you may output any of them.

Constraints and clarifications

• $3 \leq N \leq 300 \ 000$.
• $0 \leq M \leq 100 \ 000$.
• $0 \leq Ui < Vi \leq N − 1$ for each $i = 0 . . . M − 1$

Your program will be tested against several test cases grouped in subtasks. In order to obtain the score of a subtask, your program needs to correctly solve all of its test cases.

In each subtask you can obtain a partial score by correctly determining the number of pairs of connected circles having the same color in an optimal coloring.
Specifically, you get $50$ of the points of a subtask if the value of $K$ is correct in each testcase of the subtask, but there is at least one testcase where the coloring given in the second line of the output contains more than $K$ connected pairs with the same color. Note that the second line must contain a valid coloring, that is, $N$ numbers with value $0$ or $1$, otherwise you may receive an “Output isn’t correct verdict.

Example 1

stdin

5 1
0 2

stdout

1
0 0 1 0 1

Explanation

In the first sample case, the image with the extra line connecting circles $0$ and $2$ is displayed in the following figure.

It can be proved that it is not possible to color the circles such that every connected pair has different colors. For example, at least two out of circles $0, 1$ and $2$ will always have the same color.

However, it is possible to color the circles such that only one connected pair has the same color. There are exactly four such colorings, two of them are displayed in the figure below.

Example 2

stdin

9 3
1 8
2 4
5 7

stdout

3
0 1 0 1 0 1 1 0 1