보도블록

연아와 연재는 아래 그림과 같은 보도블록 지역에서 자주 논다. M개의 행과 N개의 열로 이루어진 M×N 보도블록은 모두 2MN개의 타일로 이루어져 있다. 각 타일은 짧은 변과 긴 변의 길이 비가 1:2인 같은 크기의 직사각형이며, 색은 흰색과 회색 두 가지이다.

그림 1(a). 2×3 보도블록

그림 1(b). 4×4 보도블록

M×N 보도블록의 행은 위에서 아래로 1부터 M까지, 열은 왼쪽에서 오른쪽으로 1부터 N까지 번호가 매겨져 있다. i행 j열에는 서로 다른 색의 타일 두 개가 정사각형 모양으로 맞붙어 있으며, 배치 모양은 i+j의 홀짝에 따라 정해진다.

1. i+j가 짝수이면 두 타일은 위아래로 놓이고, 위쪽 타일이 흰색이다.
2. i+j가 홀수이면 두 타일은 좌우로 놓이고, 왼쪽 타일이 흰색이다.

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

연아와 연재가 하는 게임은 다음과 같다. 보도블록의 크기를 정한 뒤, 그 안의 타일 하나에서 출발한다. 이후 아래 조건을 지키며 가능한 한 많은 서로 다른 타일을 밟고 지나 출발한 타일로 돌아와야 한다.

1. 출발 타일은 임의로 고를 수 있다.
2. 출발 타일을 제외한 모든 타일은 최대 한 번만 밟을 수 있다. 출발 타일은 처음과 끝에 한 번씩 밟는다.
3. 한 타일에서 다음 타일로 이동할 때는 반드시 변을 공유하는 타일로만 이동해야 한다. 따라서 한 타일에서 바로 이동할 수 있는 타일은 최대 5개이다. 예를 들어 그림 1(a)의 1행 2열 흰색 타일에서는 오른쪽 회색 타일, 아래쪽 흰색 타일, 왼쪽의 흰색 또는 회색 타일로 이동할 수 있다.

그림 1(a)의 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) → (1,1,1)

보도블록의 크기 M×N이 주어질 때, 밟을 수 있는 타일 수의 최댓값과 그 최댓값을 얻는 타일 방문 순서를 출력하는 프로그램을 작성하시오.

첫째 줄에 보도블록의 행 수 M과 열 수 N을 나타내는 두 정수가 공백으로 구분되어 주어진다. (2 ≤ M, N ≤ 100)

첫째 줄에 밟고 지날 수 있는 타일 수의 최댓값 K를 출력한다. 다음 K개의 줄에는 출발점부터 시작해 밟는 순서대로 타일을 하나씩 출력한다. 마지막에 다시 돌아오는 출발 타일은 출력하지 않는다. 각 줄에는 타일을 나타내는 세 정수 i, j, c를 공백으로 구분해 출력한다. 여기서 i는 행 번호, j는 열 번호, c는 색을 나타내며 0 또는 1이다.