Задача Q. Обход в глубину

Автор:Жюри ВКОШП-2008   Ограничение времени:2 сек
Входной файл:dfs.in   Ограничение памяти:256 Мб
Выходной файл:dfs.out  

Условие

Недавно на кружке по программированию Петя узнал об обходе в глубину. Обход в глубину используется во многих алгоритмах на графах. Петя сразу же реализовал обход в глубину на своих любимых языках программирования — паскале и си.


var
  a: array [1..maxn, 1..maxn] 
       of boolean;
  visited: array [1..maxn] 
       of boolean;

procedure dfs(v: integer);
var 
  i: integer;
begin
  writeln(v);
  visited[v] := true;
  for i := 1 to n do begin
    if a[v][i] and 
        not visited[i] then 
    begin
      dfs(i);
      writeln(v);
    end;
  end;
end;

procedure graph_dfs;
var
  i: integer;
begin
  for i := 1 to n do
    if not visited[i] then
    	dfs(i);
end;

int a[maxn + 1][maxn + 1];
int visited[maxn + 1];

void dfs(int v) {
  printf("%d\n", v);
  visited[v] = 1;
  for (int i = 1; i <= n; i++) {
    if ((a[v][i] != 0) && 
        (visited[i] == 0)) {
      dfs(i);
      printf("%d\n", v);
    }
  }
}

void graph_dfs() {
  for (int i = 1; i <= n; i++) {
    if (visited[i] == 0) {
      dfs(i);
    }
  }
}

Петина программа хранит граф с использованием матрицы смежности в массиве "a" (вершины графа пронумерованы от 1 до n). В массиве "visited" помечается, в каких вершинах обход в глубину уже побывал.

Петя запустил процедуру "graph_dfs" для некоторого неориентированного графа G с n вершинами и сохранил ее вывод. А вот сам граф потерялся. Теперь Пете интересно, какое максимальное количество ребер могло быть в графе G. Помогите ему выяснить это!

Формат входного файла

Первая строка входного файла содержит два целых числа: n и l — количество вершин в графе и количество чисел в выведенной последовательности. Следующие l строк по одному числу — вывод Петиной программы. Гарантируется, что существует хотя бы один граф, запуск программы Пети на котором приводит к приведенному во входном файле выводу.

Формат выходного файла

На первой строке выходного файла выведите одно число m — максимальное возможное количество ребер в графе. Следующие m строк должны содержать по два целых числа — номера вершин, соединенных ребрами. В графе не должно быть петель и кратных ребер.

Ограничения

1 ≤ n ≤ 300

1 ≤ l ≤ 2n − 1

Примеры тестов

Входной файл (dfs.in) Выходной файл (dfs.out)
1
6 10
1
2
3
2
4
2
1
5
6
5
6
1 2
1 3
1 4
2 3
2 4
5 6

0.061s 0.011s 13