Problem Description

There are $n$ points arranged from left to right, numbered $1,2,\dots,n$.

You need to add some edges between them, and denote the edge set as $E=\{(x,y)\ |\ 1\leq x<y\leq n\}$.

We say that the edge set $E$ satisfies the constraint $[l,r]$ if and only if there exists $(x,y)\in E$ such that $[x\in[l,r]]+[y\in[l,r]]=1$.

Basically, we require that for all $1\leq i\leq n$, the constraint $[i,i]$ is satisfied.

On top of that, the input gives $m$ additional constraints $[l_i,r_i]$ ($1\leq l_i<r_i\leq n$ and $[l_i,r_i]\neq [1,n]$).

What is the minimum possible $|E|$? Also, based on that, output one valid construction. It can be proven that a valid $E$ always exists.

For an expression of the form $[P]$, its value is $1$ if and only if the proposition $P$ is true; otherwise, its value is $0$.

Input Format

The first line contains two integers $n,m$.

The next $m$ lines each contain two positive integers $l_i,r_i$.

Output Format

The first line output one number representing $|E|$.

The next $|E|$ lines each contain two numbers $x,y$ representing an edge. Note that you must ensure $1\le x<y\le n$.

4 3
1 2
3 4
1 2

2
1 4
2 3

Hint

Sample Explanation

For the constraint $[1, 1]$, there is an edge $(1, 4)$ such that $[1 \in [1, 1]] + [4 \in [1, 1]] = 1$.

For the constraint $[3, 4]$, there is an edge $(1, 4)$ such that $[1 \in [3, 4]] + [4 \in [3, 4]] = 1$.

For the constraint $[2, 2]$, there is an edge $(2, 3)$ such that $[2 \in [2, 2]] + [3 \in [2, 2]] = 1$.

Constraints

For all testdata, it is guaranteed that $3\leq n\leq 10^4$, $0\leq m\leq 10^5$, $1\le l_i<r_i\le n$, and $[l_i,r_i]\ne [1,n]$.

For the $i$-th test point, it is guaranteed that the parity of $n$ is the same as the parity of $i$, and the parity of $m$ is the same as the parity of $\lfloor\frac{i}{2}\rfloor+1$.

Translated by ChatGPT 5