Error Report

A function call stack trace printed when an error occurs is a powerful tool for debugging programs. Consider a mathematical model of how functions in a program interact, called a call graph.

Suppose a program has $n$ functions that can call one another. Number all functions in the program from 1 to $n$. Let $E$ be the set of pairs $(f_i, g_i)$, where $f_i$ and $g_i$ are the numbers of functions such that $f_i$ calls $g_i$. The size of this set is called the complexity of the call graph.

For example, consider a program in a primitive programming language with three functions.

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

Number the functions so that $f$ is 1, $g$ is 2, and $h$ is 3. Then the set $E$ is $E = \{(1, 2), (1, 3), (3, 3)\}$ because function $f$ calls functions $g$ and $h$, function $g$ calls no other functions, and function $h$ calls itself. The complexity of the call graph of this program is 3.

The call stack trace printed when an error occurs works as follows. Suppose some error occurs while the program is running. First, the number of the function $i_1$ in which the error occurred is printed, then the number of the function $i_2$ from which this function $i_1$ was directly called, then the number of the function $i_3$ from which function $i_2$ was called, and so on.

For example, suppose the call $f(-3)$ is made in the program above. Then $h(-3)$ is called, which calls $h(-2)$, which in turn calls $h(-1)$ and $h(0)$, and division by 0 occurs in the last call. Then the call stack trace looks like this:

3
3
3
3
1

Yura asked Lyosha to find an error in his program and sent him the call stack traces printed after errors. Unfortunately, the file Yura sent to Lyosha contains several call stack traces from different errors, and these traces are printed one after another with no separators between them. Yura claims that errors can occur in only two functions, but he does not remember which ones.

Lyosha realized that the call stack traces alone would not be enough and that he would have to look at the program. Before doing so, he wants to find out what minimum complexity the call graph of this program can have if all of Yura's claims are true.

Help him find the minimum possible complexity of the program's call graph such that the file sent to him could contain one or more call stack traces written one after another without separators, and the direct errors occurred in at most two different functions.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 1000$): the number of functions in Yura's program and the number of lines in the call stack trace file that Yura sent to Lyosha. Each of the following $m$ lines contains a single integer $f_i$ ($1 \le f_i \le n$): the number of the function on the $i$-th line of the file.

On the first line, print a single integer $k$: the minimum possible complexity of the call graph of Yura's program. On each of the following $k$ lines, print two integers $a_i$ and $b_i$. Such a pair means that the function numbered $a_i$ can call the function numbered $b_i$. If there are several possible call graphs, print any one of them.

In the example, it is possible that errors occur only in functions 1 and 3, and that the given file contains five call stack traces written one after another. Below are the same traces separated by empty lines.

1
 
3
 
3
2
 
3
2
 
1

In this case only function 2 calls function 3, so the complexity of the call graph is 1.