오류 보고서

함수 호출 스택을 출력한 오류 보고서는 프로그램 디버깅에 강력한 도구다. 프로그램 안 함수들 사이의 상호 작용을 수학적으로 모델링한 것을 호출 그래프라고 한다.

프로그램에 서로를 호출할 수 있는 $n$개의 함수가 있다고 하자. 프로그램의 모든 함수에 1부터 $n$까지 번호를 붙인다. $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$를 1번, $g$를 2번, $h$를 3번이라고 하자. 그러면 집합 $E$는 $E = \{(1, 2), (1, 3), (3, 3)\}$이다. 함수 $f$는 $g$와 $h$를 호출하고, 함수 $g$는 다른 함수를 호출하지 않으며, 함수 $h$는 자기 자신을 호출하기 때문이다. 이 프로그램의 호출 그래프 복잡도는 3이다.

오류가 발생했을 때 호출 스택을 출력하는 방식은 다음과 같다. 프로그램을 실행하는 도중에 오류가 발생했다고 하자. 먼저 오류가 발생한 함수 $i_1$의 번호가 출력되고, 그다음 이 함수 $i_1$을 직접 호출한 함수 $i_2$의 번호가 출력되며, 그다음 함수 $i_2$를 호출한 함수 $i_3$의 번호가 출력되는 식이다.

예를 들어 위 프로그램에서 $f(-3)$을 호출했다고 하자. 그러면 $h(-3)$이 호출되고, 이어서 $h(-2)$, 그다음 $h(-1)$과 $h(0)$이 호출되며, 마지막 호출에서 0으로 나누게 된다. 이때 호출 스택을 출력하면 다음과 같다.

3
3
3
3
1

유라는 자신의 프로그램에서 오류를 찾아 달라고 요청하면서 오류가 발생한 뒤의 호출 스택 출력을 레샤에게 보냈다. 아쉽게도 유라가 보낸 파일에는 서로 다른 오류에 대한 호출 스택 출력이 여러 개 들어 있고, 이 출력들은 아무 구분자 없이 연달아 나열되어 있다. 유라는 오류가 두 함수에서만 발생할 수 있다고 주장하지만, 어느 함수인지는 기억하지 못한다.

레샤는 호출 스택 출력만으로는 부족하다는 것을 깨닫고 프로그램을 직접 봐야 한다고 판단했다. 하지만 그러기 전에, 유라의 주장이 모두 맞다는 전제 아래 이 프로그램의 호출 그래프가 가질 수 있는 최소 복잡도를 알아내려고 한다.

유라가 보낸 파일이 구분자 없이 연달아 기록된 하나 이상의 호출 스택 출력을 담고 있을 수 있고, 직접적인 오류가 두 개 이하의 서로 다른 함수에서 발생했다면, 프로그램의 호출 그래프가 가질 수 있는 최소 복잡도를 구하자.

첫째 줄에 정수 $n$과 $m$이 주어진다($1 \le n, m \le 1000$). $n$은 유라의 프로그램에 있는 함수의 수이고, $m$은 유라가 레샤에게 보낸 호출 스택 출력 파일의 줄 수이다. 다음 $m$개 줄에 정수 $f_i$가 하나씩 주어진다($1 \le f_i \le n$). $f_i$는 파일의 $i$번째 줄에 있는 함수의 번호이다.

첫째 줄에 정수 $k$를 출력한다. $k$는 유라의 프로그램 호출 그래프가 가질 수 있는 최소 복잡도이다. 다음 $k$개 줄에 정수 $a_i$와 $b_i$를 출력한다. 이 쌍은 $a_i$번 함수가 $b_i$번 함수를 호출할 수 있다는 뜻이다. 가능한 호출 그래프가 여러 개라면 아무거나 출력한다.

예에서 오류가 함수 1과 3에서만 발생하고, 주어진 파일에 다섯 개의 호출 스택 출력이 연달아 기록되어 있을 수 있다. 아래는 같은 출력을 빈 줄로 구분한 것이다.

1
 
3
 
3
2
 
3
2
 
1

이때 함수 2만 함수 3을 호출하므로 호출 그래프의 복잡도는 1이다.