사탄 게임

뱀과 사다리는 유명한 주사위 게임이다. 처음에 말은 보드 바깥에 있다. 턴이 시작될 때 $M$면체 주사위를 굴린다. 1 이상 $M$ 이하의 자연수가 각각 $1/M$의 확률로 나온다. 나온 수만큼 말을 전진시키고(보드 바깥에 있으면 나온 수에 해당하는 칸으로 이동한다), 그 칸에 뱀이나 사다리가 있으면 가리키는 칸으로 옮긴다. 말이 $N$번 칸에 도달하면 게임이 끝난다. $N$번 칸을 넘어가도 도착으로 본다.

이런 문제를 생각해볼 수 있다. "도착하기까지 주사위를 굴려야 하는 횟수의 기댓값은 얼마일까?" 하지만 우리는 이 문제를 푸는 것이 아니라, 이 문제의 테스트케이스를 만들어야 한다.

답이 50,000,000,000,000,000,000 이상인 테스트케이스를 만들어 보자.

입력은 없다.

첫 줄에 자연수 $N$, $M$, $S$를 출력한다. $N$은 100 이하, $M$은 20 이하, $S$는 $N/2$ 이하여야 한다.

다음 $S$줄에는 한 줄에 하나씩 뱀이나 사다리의 시작점과 도착점을 출력한다. 도착점이 시작점보다 작으면 뱀, 크면 사다리이다. 시작점은 1 이상 $N-1$ 이하, 도착점은 1 이상 $N$ 이하여야 한다. 모든 시작점과 도착점 중에 중복되는 점은 없어야 한다.

말이 어느 칸에 놓여 있어도 게임을 끝낼 수 있음이 보장되어야 한다. 도달 자체가 불가능한 칸에 일부러 말을 놓거나, 뱀이나 사다리의 시작점에 말을 올려놓고 타지 않은 채로 시작해도 게임을 끝낼 수 있어야 한다. 전혀 이해할 수 없는 조건이지만, 구데기컵이니까 그러려니 하자.