Недавно на кружке по программированию Петя узнал об обходе в глубину.
Обход в глубину используется во многих алгоритмах на графах. Петя сразу
же реализовал обход в глубину на своих любимых языках программирования —
паскале и си.
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 строк должны содержать по два
целых числа — номера вершин, соединенных ребрами. В графе не должно быть
петель и кратных ребер.
