사회적 거리두기

NYPC 2020 · 예선

배찌가 다니고 있는 크아중학교의 교실은 N×NN \times N 크기의 격자판으로 표현할 수 있다. 각 격자 칸에는 학생이 앉을 수 있는 자리가 마련되어 있다. 학교 선생님들은 각 학생이 앉은 자리로부터 앞쪽, 뒤쪽, 왼쪽, 오른쪽, 대각선으로 인접한 자리에 다른 학생이 붙어 앉지 못하도록 자리 배치를 해야 한다. 그러나 교실의 일부 격자 칸에 놓인 책상은 망가져 있어서 학생이 앉을 수 없는 상태다. 선생님은 교실에 최대한 많은 학생을 앉히고 싶어 한다.

<그림 1> 교실을 나타내는 격자판
<그림 1> 교실을 나타내는 격자판

위 <그림 1>을 보자. 교실의 크기는 5×55 \times 5이며, 격자 칸 44개에 놓인 책상이 망가져 있다. 이때, 최대한 많은 자리를 확보하면 아래 <그림 2>처럼 88개의 자리를 확보할 수 있다.

<그림 2> 가장 많은 자리를 확보한 예시
<그림 2> 가장 많은 자리를 확보한 예시

선생님의 입장이 되어 교실의 크기와 망가진 책상 위치들의 정보가 주어졌을 때, 최대한 많은 자리를 확보해보자.

입력 형식

첫 줄에 교실의 크기를 나타내는 정수 NN과 망가진 책상의 수를 나타내는 정수 KK가 공백으로 구분되어 주어진다. (5≤N≤18;(5 \le N \le 18; 0≤K≤N2)0 \le K \le N^2)

그 다음 KK 개의 줄에 걸쳐 망가진 책상이 놓인 격자 칸의 위치 정보를 나타내는 정수 rr와 cc가 공백으로 구분되어 주어진다. 이는 rr 행, cc 열의 격자 칸에 있는 책상이 망가져 학생이 앉을 수 없음을 의미한다. (1≤r,c≤N)(1 \le r, c \le N)

주어지는 격자 칸의 위치는 서로 겹치지 않는다.

출력 형식

첫 줄에 최대한 많이 확보한 자리의 개수 SS를 출력한다.

그리고 다음 SS 개의 줄에 걸처 확보한 자리의 위치 정보를 나타내는 정수 rr와 cc를 공백을 사이에 두고 출력한다.

만약, 가능한 답이 여러 가지인 경우 그중 아무거나 하나 출력한다.

예제

입력

5 4
2 2
2 5
4 3
5 1

출력

8
1 1
1 3
1 5
3 1
3 3
3 5
5 3
5 5

채점 방식

이 문제는 풀이 소스 코드를 제출하지 않고, 각 테스트 케이스의 입력 데이터를 다운받아 알맞은 출력 파일을 만들어 출력 파일만을 제출하는 문제다.

문제 해결을 도와주는 시뮬레이터가 아래 미션에 대해 제공된다. 제공되는 시뮬레이터는 최신 버전의 크롬 브라우저에서 여는 것을 권장한다.

해설