---
# System prepended metadata

title: King's Commands
tags: [statement]

---

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

![image](https://hackmd.io/_uploads/r1mxruNqC.png)



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:

![image](https://hackmd.io/_uploads/r1mxruNqC.png)

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

