Seat Assignment

A big match is played next week. The stadium has $N$ seats, numbered $1$ through $N$. A fan who requests a ticket also states the range of seats the fan is willing to sit in. The range is given by two integers $F$ and $L$, and the fan accepts any seat $S$ with $F \le S \le L$.

The ticket office has received $M$ requests. Two fans cannot get the same seat. Compute the largest number of requests that can be satisfied at the same time, and print a seat assignment for that many requests.

The first line contains the number of seats $N$ ($1 \le N \le 100000$) and the number of requests $M$ ($1 \le M \le 1000000$), separated by a space.

Each of the next $M$ lines contains one request as two integers $F$ and $L$ ($1 \le F \le L \le N$). Requests are numbered $1$ through $M$ in the order they appear in the input.

Print the largest number of selected requests $K$ on the first line.

On each of the next $K$ lines print one seat assignment, in increasing order of seat number. Each line holds the seat number $S$ and the number $R$ of the request that gets seat $S$, separated by a space.

Several assignments reach the maximum, so only the assignment fixed by the following rule is accepted. Scan the seats from $1$ to $N$. For the seat $S$ under consideration, collect the requests that have no seat yet and satisfy $F \le S \le L$. If there is at least one such request, give seat $S$ to the one with the smallest $L$. If two or more of them share the same $L$, give the seat to the one with the smallest request number. If there is no such request, leave seat $S$ empty.

This rule always reaches the largest possible number of satisfied requests.