题目描述

从左到右排列着 $n$ 个点，编号分别为 $1,2,\dots,n$。

你要在他们之间连一些边，记边集为 $E=\{(x,y)\ |\ 1\leq x<y\leq n\}$。

我们称边集 $E$ 满足限制 $[l,r]$，当且仅当存在 $(x,y)\in E$ 使得 $[x\in[l,r]]+[y\in[l,r]]=1$。

基础地，我们希望对所有 $1\leq i\leq n$ 满足限制 $[i,i]$。

在此基础上，输入还给定了额外的 $m$ 个限制 $[l_i,r_i]$（$1\leq l_i<r_i\leq n$ 并且 $[l_i,r_i]\neq [1,n]$）。

请问 $|E|$ 最小是多少，在此基础上给出一组合法构造。可以证明，合法的 $E$ 总是存在的。

对于形如 $[P]$ 的表达式，当且仅当命题 $P$ 为真时其取值为 $1$，否则取值为 $0$。

输入格式

第一行输入两个整数 $n,m$。

接下来 $m$ 行每行两个正整数 $l_i,r_i$。

输出格式

第一行输出一个数代表 $|E|$。

接下来 $|E|$ 行，每行两个数 $x,y$ 代表一条边，注意你需要保证 $1\le x<y\le n$。

4 3
1 2
3 4
1 2

2
1 4
2 3

提示

样例解释

对于限制 $[1, 1]$，存在边 $(1, 4)$ 使得 $[1 \in [1, 1]] + [4 \in [1, 1]] = 1$。

对于限制 $[3, 4]$，存在边 $(1, 4)$ 使得 $[1 \in [3, 4]] + [4 \in [3, 4]] = 1$。

对于限制 $[2, 2]$，存在边 $(2, 3)$ 使得 $[2 \in [2, 2]] + [3 \in [2, 2]] = 1$。

数据范围

对于所有数据，保证 $3\leq n\leq 10^4$，$0\leq m\leq 10^5$，$1\le l_i<r_i\le n$，$[l_i,r_i]\ne [1,n]$。

对于第 $i$ 个测试点，保证 $n$ 的奇偶性与 $i$ 的奇偶性相同，$m$ 的奇偶性与 $\lfloor\frac{i}{2}\rfloor+1$ 的奇偶性相同。