보도블록 Batch Compilation commands

연아와 연재는 아래 그림과 같은 모양으로 보도블록이 깔린 지역에서 자주 놀곤 한다. $M$개의 행과 $N$개의 열로 이루어진 $M \times N$ 크기의 보도블록은 $2MN$개의 타일들로 구성되는데, 이 타일들은 짧은 변과 긴 변의 길이 비가 $1:2$인 직사각형 모양으로 크기가 동일하고, 색은 흰색과 회색 두 종류가 있다.

$MN$ 크기의 보도블록에서 각 행은 위에서 아래로 $1$부터 $M$까지 번호가 매겨져 있고, 각 열은 왼쪽에서 오른쪽으로 $1$부터 $N$까지 번호가 매겨져 있다고 하자. $i$행 $j$열에는 색이 다른 두 타일이 정사각형 모양으로 맞붙어 배치되어 있는데, 배치된 모양은 $i+j$ 의 값에 따라 다음 두 가지 중 하나이다.

1. $i+j$ 의 값이 짝수이면, 그림 1(a)의 $1$행 $1$열처럼 두 타일이 가로로 배치되어 있으며 위의 것이 흰색이다.
2. $i+j$ 의 값이 홀수이면, 그림 1(a)의 $1$행 $2$열처럼 두 타일이 세로로 배치되어 있으며 왼쪽의 것이 흰색이다.

$i$행 $j$열의 흰색 타일은 $(i,j,0)$으로 나타내고 회색 타일은 $(i,j,1)$로 나타낸다.

연아와 연재는 이 보도블록에서 자주 게임을 하는데, 이 게임의 규칙은 간단하다. 먼저 보도블록의 크기를 정한다. 그런 다음 이 보도블록에 속한 타일 하나에서 출발하여 아래의 조건을 만족하면서 가능한 많은 개수의 타일을 밟고 지나서 다시 출발한 타일로 되돌아오는 게임이다.

1. 출발하는 타일은 임의로 정할 수 있다.
2. 하나의 타일은 정확히 한번만 밟고 지날 수 있다. 단, 출발한 타일은 출발할 때와 도착할 때 한 번씩 두 번 밟게 된다.
3. 한 타일에서 다음 타일로 이동할 때 반드시 변을 맞대고 있는 타일로 이동해야 한다. 따라서 한 타일에서 이동 가능한 타일은 최대 5개이다. 예를 들면, 그림 1(a)의 $1$행 $2$열에 있는 흰색 타일에서는 바로 오른쪽 회색 타일, 바로 아래 흰색 타일, 바로 왼쪽의 흰색 또는 회색 타일로만 이동 가능하다.

예를 들어 그림 1(a)와 같이 $2 \times 3$크기의 보도블록에서는 다음과 같은 방법으로 12개의 타일을 모두 지날 수 있다.

$(1,1,1)$ $\rightarrow$ $(1,1,0)$ $\rightarrow$ $(1,2,0)$ $\rightarrow$ $(1,2,1)$ $\rightarrow$ $(1,3,0)$ $\rightarrow$ $(1,3,1)$ $\rightarrow$ $(2,3,1)$ $\rightarrow$ $(2,3,0)$ $\rightarrow$ $(2,2,0)$ $\rightarrow$ $(2,2,1)$ $\rightarrow$ $(2,1,1)$ $\rightarrow$ $(2,1,0)$ $\rightarrow$ $(1,1,1)$

보도블록의 크기 $M \times N$이 주어질 때 최대 몇 개의 타일을 지날 수 있는지, 그리고 어떤 순서로 타일을 지나야 최대 개수의 타일을 지나게 되는지를 알아내는 프로그램을 작성하시오.

프로그램의 실행시간은 1초를 넘을 수 없고, 각 채점 데이터의 부분 점수는 없다.

서브태스크

서브태스크 1 (4.4점)

• $2 \le N, M \le 10$
• 맞은 데이터의 수에 비례하게 점수가 주어집니다.

서브태스크 2 (17.6점)

• $2 \le N, M \le 100$
• 맞은 데이터의 수에 비례하게 점수가 주어집니다.

입력 형식

첫째 줄에 보도블록의 행의 개수 $M$과 열의 개수 $N$을 나타내는 두 개의 정수가 빈칸을 사이에 두고 주어진다.

출력 형식

첫째 줄에 밟고 지날 수 있는 타일의 최대 개수 $K$를 출력한다. 다음 $K$개의 줄에, 밟고 지나는 순서대로 출발점부터 시작하여 $K$개의 타일들을 한 줄에 하나씩 출력한다. (마지막에 돌아온 출발점은 다시 출력하지 않는다.) 하나의 줄에는 하나의 타일을 나타내는 3개의 정수 $i, j,c$ 를 빈칸을 사이에 두고 출력한다. 여기서, $i$는 타일의 행 번호, $j$는 타일의 열 번호, $c$ ($0$ 또는 $1$)는 타일의 색을 나타낸다.

입력과 출력의 예

입력

2 3

출력

12
1 1 1
1 1 0
1 2 0
1 2 1
1 3 0
1 3 1
2 3 1
2 3 0
2 2 0
2 2 1
2 1 1
2 1 0