# King's Commands

https://dmoj.ca/problem/dmopc21c7p5

There are a total of $2N$ cities, with $N$ cities evenly spaced on both sides of a forest. The cities are numbered $(1,0)$ to $(N,0)$ on one side of the forest, and $(1,1)$ to $(N,1)$ on the other side of the forest.

In order to connect the city, the King has given you $M$ commands to the build bridges. In the $i$-th command, he instructs you to build a bridge between city $a_i$ and $b_i$ on opposite sides of the forest. There are two possible interpretations of his instructions:

- **Interpretation 0**: Build a bridge between cities $(a_i,0)$ and $(b_i, 1)$
- **Interpretation 1**: Build a bridge between cities $(a_i,1)$ and $(b_i, 0)$

Additionally, it is known that **Each city number appears at most twice in the list**. Meaning that for any integer $x$, $x$ can appear at most twice among the $2M$ integers given by the king.

A bridge between city $x$ and $y$ allows us to travel in both directions between $x$ and $y$. Additionally, if two bridges intersect, we can transfer from one bridge to the other. More formally, given two bridges $(a,0)- (b,1)$ and $(c,0) - (d,1)$ satisfying $a \leq c$, we say they intersect if and only if $b \geq d$.

For example, in the below diagram, it is possible to travel from $(2,1)$ to $(5,2)$ via the path highlighted in red. The bridges $(2,0) - (3,1)$ and $(4,0) - (2,1)$ intersect so we can transfer between the two bridges.


Two cities are connected if we can travel between them using the bridges. The disconnectedness of the city is defined as the size of the largest set of cities $S$, such that for any two cities in $S$, they are not connected. You are to decide which interpretation to choose for each of the $M$ commands, such that the disconnectedness of the city is minimiezd.

# Constraints

- $1 \leq N, M \leq 10^6$
- $1 \leq a_i, b_i \leq M$
- Each number from $1$ to $N$ appears at most twice among all values $2M$ of $a$ and $b$

# Subtasks

1. (10 points) $M \leq 20$
2. (30 points) $M \leq 5000$
3. (30 points) Each number from $1$ to $N$ appears **at most once** among all values $2M$ of $a$ and $b$
4. (30 points) No additional constraints

# Input

The first line contains two integers, $N$ and $M$.

The next $M$ line contains two integers each, $a_i$ and $b_i$.

# Output

Output a single integer on the first line, the minimum possible disconnectedness

Then, output a space-separated sequence of $M$ integers $0$ or $1$, where the $i$-th integer is the interpretation of the $i$th command. These bridges must achieve the minimum disconnectedness. If there are many possible ways, you may print any of them

# Sample

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

The following are the bridges built:


The disconnectedness of this configuration is $6$, which is the minimum possible.