题目描述

错误发生时的函数调用栈打印是强大的调试工具。考虑程序中函数之间交互的数学模型，称为调用图。

设程序中有 $n$ 个函数，编号为 $1$ 到 $n$。考虑有向边集合 $E$，其中一条边 $(f_i,g_i)$ 表示函数 $f_i$ 可以调用函数 $g_i$。集合 $E$ 的大小称为调用图的复杂度。

例如，考虑如下伪代码程序：

function f(x)
    if x > 0 then
        return g(x)
    else
        return h(x)

function g(x)
    return x

function h(x)
    if x == 0 then
        return 1 / x
    else
        return h(x + 1) + 1

若函数 $f,g,h$ 分别编号为 $1,2,3$，则调用边集合为

复杂度为 $3$。

错误发生时的调用栈打印如下：先输出发生错误的函数编号 $i_1$，然后输出直接调用 $i_1$ 的函数编号 $i_2$，再输出调用 $i_2$ 的函数编号 $i_3$，依此类推。

例如，上述程序执行 $f(-3)$ 时，调用过程会到达 $h(0)$ 并发生除以零错误，调用栈打印为：

3
3
3
3
1

Yura 请求 Lesha 帮忙找程序错误，给他发来了若干次错误后的调用栈打印。遗憾的是，这些调用栈被直接连续写在一个文件中，之间没有任何分隔符。同时 Yura 声称错误只可能发生在不超过两个不同函数中，但他不记得具体是哪两个。

Lesha 明白只靠调用栈不够，还要看程序。但在此之前，他想知道：若 Yura 的说法都正确，则该程序调用图的最小可能复杂度是多少。

请构造一个复杂度最小的调用图，使得给定文件可以看作一个或多个连续拼接的调用栈打印，并且直接发生错误的函数不超过两个。

输入格式

第一行包含两个整数 $n,m$，表示程序函数数和文件中的行数。

接下来 $m$ 行，每行包含一个整数 $f_i$，表示文件第 $i$ 行中的函数编号。

数据范围：

• $1 \le n,m \le 100000$；
• $1 \le f_i \le n$。

输出格式

第一行输出一个整数 $k$，表示调用图的最小可能复杂度。

接下来 $k$ 行，每行输出两个整数 $a_i,b_i$，表示函数 $a_i$ 可以调用函数 $b_i$。

如果有多个最优调用图，输出任意一个。

样例输入

3 7
1
3
3
2
3
2
1

样例输出

1
2 3

样例解释

样例中可以认为错误只发生在函数 $1$ 和 $3$ 中，文件由五段调用栈拼接而成：

1

3

3
2

3
2

1

此时只有函数 $2$ 调用函数 $3$，复杂度为 $1$。