Candy Machine

In a candy factory, there is a mysterious candy machine that produces unique candies. The machine has a row of output slots numbered from $1$ to $n$. Before production begins, it prints a schedule that specifies the release time and the slot number for each candy.

To collect all the candies without them falling and breaking, the factory boss can install automated collection cars underneath the slots. Each car can move from one slot to an adjacent one in one second, and before production begins, it can be positioned at any slot. However, since installation costs are extremely high, the boss wants to use as few cars as possible.

A candy released at time $t$ from slot $x$ can be caught by a car that previously caught a candy at time $t_0$ from slot $x_0$ if and only if $$t-t_0\geq |x-x_0|.$$

Given the schedule, determine the minimum number of cars required and assign each candy to a car such that every candy is collected.

inputFormat

The first line contains two integers $n$ and $m$, where $n$ is the number of slots and $m$ is the number of candies.

The following $m$ lines each contain two integers $t$ and $x$, representing the release time and the slot index of a candy, respectively.

outputFormat

Output the minimum number of collection cars required on the first line. Then output $m$ lines, where the $i$-th line contains the ID of the car that collects the $i$-th candy (in the order of the input).

sample

5 3
1 1
2 3
3 2

2
1
2
1