부정행위 멈춰!

면접 대비

시간 제한2초메모리 제한1024 MB

요약

N행 M열 격자의 각 칸에 시험지 종류를 배정합니다. 변이나 꼭짓점으로 맞닿은 칸끼리는 같은 종류가 되지 않도록 종류 수를 최소로 정합니다.

난이도: 쉬움10점 중 3점
유형: 구현, 수학
정답자: 아직 제출이 없습니다

문제

김채완 교수는 「프로그래밍과 봉사」 과목의 기말고사를 준비하고 있다. 고사실은 가로 $M$ 칸, 세로 $N$ 칸인 직사각형이며, 모든 칸에 학생이 정확히 한 명씩 앉는다. 김채완 교수는 부정행위를 막기 위해 인접한 학생끼리 서로 다른 시험지를 받도록 여러 종류의 시험지를 준비하려 한다. 이때 인접한 학생은 가로, 세로, 또는 대각선으로 붙어 있는 칸에 있는 학생을 뜻한다.

김채완 교수는 시험지를 많이 준비할 시간이 없었기 때문에 시험지의 종류를 최소화하고자 한다. 가능한 한 적은 종류의 시험지를 사용해 조건을 만족하도록 시험지를 배부하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 $N$ , $M$ 이 공백으로 구분되어 주어진다. $(1 \leq N, M \leq 1\,000)$

출력

첫째 줄에 사용한 시험지의 종류 수 $K$ 를 출력한다. 둘째 줄부터 $N$ 개의 각 줄에 $1$ 이상 $K$ 이하의 정수 $M$ 개를 공백으로 구분하여 출력한다. 각 정수는 해당 칸에 배부된 시험지의 번호이다. 즉, $y+1$ 번째 줄의 $x$ 번째 정수는 위에서 $y$ 번째, 왼쪽에서 $x$ 번째 칸에 배부된 시험지의 번호이다.

힌트

입출력 양이 많으므로 문제지 2-4페이지의 언어 가이드에 있는 빠른 입출력을 사용하는 것을 권장한다.

예제2

예제 1
입력
```
3 4
```
예상 출력
```
4
3 2 4 2
4 1 3 1
3 2 4 2
```
예제 2
입력
```
1 1
```
예상 출력
```
1
1
```