게임

18세기 수학자들이 즐겼다고 전해지는 게임이 있다.

세 명의 수학자가 참가하며, 그중 한 명이 진행자이다. 진행자는 먼저 양의 정수 $N$을 발표한다. 그런 다음 $1$ 이상 $N$ 이하의 서로 다른 두 정수 $X$와 $Y$를 몰래 고르고, 두 수의 합 $X + Y$를 플레이어 $S$에게, 두 수의 곱 $X \cdot Y$를 플레이어 $P$에게 각각 비밀리에 알려 준다. 각 플레이어는 자신이 받은 값 하나만 알며, 그것이 합인지 곱인지도 안다.

두 플레이어는 정해진 순서 $S$, $P$, $S$, $P$, $\dots$ 로 번갈아 말하며, 항상 $S$가 먼저 말한다. 자기 차례가 되면 플레이어는 자신이 받은 값과 지금까지 공개된 모든 발언만으로 추론하여(모든 발언은 공개된다) "나는 두 수를 안다" 또는 "나는 두 수를 모른다" 중 하나를 말한다. 어떤 플레이어가 두 수를 정확히 맞힐 수 있는 것은 가능한 쌍이 오직 하나만 남았을 때이다. 누군가 "안다"라고 말하는 순간 게임이 끝난다.

예를 들어 대화는 다음과 같이 진행될 수 있다.

• 진행자: "$N$을 $10$으로 하자." (그런 다음 $1$부터 $10$ 사이의 두 수를 골라 합을 $S$에게, 곱을 $P$에게 알려 준다)
• 플레이어 $S$: "나는 두 수를 모른다."
• 플레이어 $P$: "나는 두 수를 모른다."
• 플레이어 $S$: "나는 두 수를 모른다."
• 플레이어 $P$: "나는 두 수를 모른다."
• 플레이어 $S$: "이제 알겠다 — 당신은 $3$과 $6$을 골랐다."

$N$과 $M$이 주어진다. 여기서 $M$은 게임이 끝나기 전까지 "나는 두 수를 모른다"라는 말이 나온 총 횟수이다(따라서 마지막 "안다" 발언은 $M + 1$번째 발언이다). 진행자가 골랐을 수 있는 모든 수의 쌍을 구하여라.

한 줄에 두 정수 $N$과 $M$이 주어진다 ($2 \le N \le 200$, $0 \le M \le 100$).

첫째 줄에, 게임이 끝나기 전까지 두 플레이어가 "나는 두 수를 모른다"를 정확히 $M$번 말하도록 하는, 진행자가 $1$부터 $N$까지 중에서 골랐을 수 있는 쌍의 개수를 출력한다.

그다음 그러한 쌍들을 한 줄에 하나씩, $a < b$인 두 정수 "$a$ $b$" 형태로 출력한다. 쌍은 오름차순으로 정렬하여 출력한다. 즉 첫 번째 수를 기준으로 정렬하고, 첫 번째 수가 같으면 두 번째 수를 기준으로 정렬한다.