19894번 - Отчет об ошибках 스페셜 저지다국어

Распечатки стека вызовов функций при ошибках --- мощный инструмент отладки программ. Рассмотрим математическую модель взаимодействия между функциями в программе, которая называется граф вызовов.

Пусть в программе $n$ функций, которые могут вызывать друг друга. Обозначим все функции в программе числами от 1 до $n$. Рассмотрим множество $E$ пар чисел $(f_i, g_i)$, где $f_i$ и $g_i$ --- номера функций, такие, что $f_i$ вызывает $g_i$. Размер этого множества будем называть сложностью графа вызовов.

Например, рассмотрим пример программы на примитивном языке программирования, в которой есть три функции.

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$ имеет номер 1, $g$ имеет номер 2 и $h$ имеет номер 3. Тогда множество $E$ выглядит следующим образом: $E = \{(1, 2), (1, 3), (3, 3)\}$, так как функция $f$ вызывает функции $g$ и $h$, функция $g$ не вызывает других функций, а функция $h$ вызывает себя. Сложность графа вызовов этой программы равна 3.

Распечатка стека вызовов при ошибке устроена следующим образом. Пусть в процессе выполнения программы произошла некоторая ошибка. Сначала в распечатку выводится номер функции $i_1$, в которой произошла ошибка, далее выводится номер функции $i_2$, из которой непосредственно была вызвана эта функция $i_1$, далее номер номер функции $i_3$, из которой была вызвана функция $i_2$, и так далее.

Пусть, например, в приведенном выше примере программы был выполнен вызов $f(-3)$. Тогда будет выполнен вызов $h(-3)$, который выполнит $h(-2)$, а далее в свою очередь $h(-1)$ и $h(0)$, в последнем вызове произойдет деление на 0. Тогда распечатка стека вызовов будет выглядеть так:

3
3
3
3
1

Юра попросил Лёшу найти ошибку в его программе, прислав ему распечатку стека вызовов после ошибок. К сожалению, файл, который Юра прислал Лёше, содержит несколько распечаток стеков вызовов при различных ошибках, причем эти распечатки выведены подряд и никак не отделены друг от друга. При этом Юра утверждает, что ошибки могут происходить только в двух функциях, правда он не помнит, в каких.

Лёша понял, что ограничиться распечаткой стека вызовов не удастся, придется смотреть на программу. Но прежде чем это сделать, он хочет выяснить, какая минимальная сложность может быть у графа вызовов этой программы, если все утверждения Юры верны.

Помогите ему выяснить. какая может быть минимальная сложность графа вызовов программы, чтобы присланный ему файл мог содержать одну или несколько записанных подряд без разделителей распечаток стеков вызовов, а непосредственные ошибки происходили не более чем в двух различных функциях.

В первой строке находятся два целых числа $n$ и $m$ ($1 \le n, m \le 1000$) --- количество функций в программе Юры и количество строк в файле с распечатками стека вызовов, которые Юра прислал Лёше. В следующих $m$ строках находятся по одному целому числу $f_i$ ($1 \le f_i \le n$) --- номер функции в $i$-й строке файла.

В первой строке выведите одно целое число $k$ --- минимальную возможную сложность графа вызовов программы Юры. В следующих $k$ выведите по два целых числа $a_i$ и $b_i$ --- такая пара означает, что функция с номером $a_i$ может вызывать функцию с номером $b_i$. Если возможных вариантов графа вызовов несколько, выведите любой.

В примере возможна ситуация, что ошибки происходят только в функциях 1 и 3, а в приведенном файле содержится пять записанных подряд распечаток стеков вызовов. Ниже приведены те же распечатки, но разделенные пустой строкой.

1
 
3
 
3
2
 
3
2
 
1

В этом случае только функция 2 вызывает функцию 3, следовательно сложность графа вызовов равна 1.