The Kingdom of Belzerg consists of $2N$ cities lined up on both sides of a long and vast forest running from west to east. The $N$ cities above the forest are numbered $1$ to $N$ from left to right, and the $N$ cities below the forest are numbered in the same manner.

To increase the connectedness of the citizens and strengthen their defense against the Demon King's advancements, the King of Belzerg has ordered for $M$ roads to be paved through the forest. Specifically, he gave you a list of $M$ commands, the $i$-th saying:

Pave a road of the shortest possible length between city $a_i$ and city $b_i$ on opposite sides of the forest.

However, he did not mention which of the cities should be on which side of the forest! You took this to mean that both interpretations would be acceptable, and so you will pave the $i$-th road between city $a_i$ above the forest and city $b_i$ below the forest or between city $b_i$ above the forest and city $a_i$ below the forest.

Of course, you know the ultimate goal is to increase the connectedness of the citizens. We say that two cities are connected if it is possible for a citizen from the first city to reach the second city by walking along the paved roads, possibly passing through some other cities in the process. Here, note that if any two roads intersect at any point, it is possible for the citizen to switch from one road to the other.

As such, you wonder: out of all possible interpretations of the king's commands, what is the smallest possible size of the largest set of cities in which no two cities are connected? Naturally, you should also produce a list of roads to pave where this size is achieved.

Constraints

$1\le N,M\le {10}^6$

$1\le a_i,b_i\le N$

Each city number appears at most twice in the list.

Subtask 1 [10%]

$1\le M\le 20$

Subtask 2 [30%]

$1\le M\le 5\times {10}^3$

Subtask 3 [30%]

Each city number appears at most once in the list.

Subtask 4 [30%]

No additional constraints.

Input Specification

The first line contains $2$ integers $N$ and $M$.

The next $M$ lines each contain $2$ integers $a_i$ and $b_i$.

Output Specification

Output a single integer on the first line, the smallest possible size of the largest set of cities in which no two cities are connected.

Then, output a space-separated sequence of $M$ integers $0$ or $1$, where the $i$-th integer is $0$ if the $i$-th road should be paved between city $a_i$ above the forest and city $b_i$ below the forest, or $1$ if the road should be paved between city $b_i$ above the forest and city $a_i$ below the forest. These roads must minimize the size of the largest set of cities in which no two cities are connected. If there are multiple solutions, output any of them.

Sample Input

7 6
4 2
3 2
1 1
4 5
6 7
6 7

Sample Output

6
0 1 0 0 1 0

Explanation

A diagram of the paved roads is given below:

For example, city $2$ above the forest is connected to city $5$ below the forest by the path highlighted in red. In general, we see that the largest set of cities in which no two cities are connected has a size of $6$, and that no smaller size can be achieved. So, this is a valid output.