문제
연아와 연재는 아래 그림과 같은 모양으로 보도블록이 깔린 지역에서 자주 놀곤 한다. M개의 행과 N개의 열로 이루어진 M×N 크기의 보도블록은 2MN개의 타일들로 구성되는데, 이 타일들은 짧은 변과 긴 변의 길이 비가 1:2인 직사각형 모양으로 크기가 동일하고, 색은 흰색과 회색 두 종류가 있다.
M×N크기의 보도블록에서 각 행은 위에서 아래로 1부터 M까지 번호가 매겨져 있고, 각 열은 왼쪽에서 오른쪽으로 1부터 N까지 번호가 매겨져 있다고 하자. i행 j열에는 색이 다른 두 타일이 정사각형 모양으로 맞붙어 배치되어 있는데, 배치된 모양은 i+j의 값에 따라 다음 두 가지 중 하나이다. (A) i+j의 값이 짝수이면, 그림 1(a)의 1행 1열처럼 두 타일이 가로로 배치되어 있으며 위의 것이 흰색이다. (B) i+j의 값이 홀수이면, 그림 1(a)의 1행 2열처럼 두 타일이 세로로 배치되어 있으며 왼쪽의 것이 흰색이다. i행 j열의 흰색 타일은 (i,j,0)으로 나타내고 회색 타일은 (i,j,1)로 나타낸다.
연아와 연재는 이 보도블록에서 자주 게임을 하는데, 이 게임의 규칙은 간단하다. 먼저 보도블록의 크기를 정한다. 그런 다음 이 보도블록에 속한 타일 하나에서 출발하여 아래의 조건을 만족하면서 가능한 많은 개수의 타일을 밟고 지나서 다시 출발한 타일로 되돌아오는 게임이다.
(1) 출발하는 타일은 임의로 정할 수 있다.
(2) 하나의 타일은 정확히 한번만 밟고 지날 수 있다. 단, 출발한 타일은 출발할 때와 도착할 때 한 번씩 두 번 밟게 된다.
(3) 한 타일에서 다음 타일로 이동할 때 반드시 변을 맞대고 있는 타일로 이동해야 한다. 따라서 한 타일에서 이동 가능한 타일은 최대 5개이다.
예를 들면, 그림 1(a)의 1행 2열에 있는 흰색 타일에서는 바로 오른쪽 회색 타일, 바로 아래 흰색 타일, 바로 왼쪽의 흰색 또는 회색 타일로만 이동 가능하다.
예를 들어 그림 1(a)와 같이 크기의 보도블록에서는 다음과 같은 방법으로 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개의 타일들을 한 줄에 하나씩 출력한다. (마지막에 돌아온 출발점은 다시 출력하지 않는다.) 하나의 줄에는 하나의 타일을 나타내는 3개의 정수 i, j, c를 빈칸을 사이에 두고 출력한다. 여기서, i는 타일의 행 번호, j는 타일의 열 번호, c(0 또는 1)는 타일의 색을 나타낸다.
예제1
23 12
111
110
120
121
130
131
231
230
220
221
211
210
-----------------------------
| 2 2 | 3 | 4 | 5 5 |
|---------| | |---------|
| 1 1 | 3 | 4 | 6 6 |
|-----------------------------|
| 12 | 11 | 9 9 | 8 | 7 |
| | |---------| | |
| 12 | 11 | 10 10 | 8 | 7 |
----------------------------예제2
55 50
111
110
120
220
121
130
131
140
240
141
150
151
250
251
350
351
341
241
340
331
330
231
230
221
321
320
420
421
430
431
440
441
450
451
550
551
541
540
530
531
521
520
511
510
411
410
311
310
211
210
-------------------------------------------------
| 2 2 | 3 | 5 | 6 6 | 8 | 10 | 11 11 |
|---------| | |---------| | |---------|
| 1 1 | 3 | 5 | 7 7 | 8 | 10 | 12 12 |
|-------------------------------------------------|
| 50 | 49 | 4 4 | 23 | 22 | 9 9 | 13 | 14 |
| | |---------| | |---------| | |
| 50 | 49 | 24 24 | 23 | 22 | 18 18 | 13 | 14 |
|-------------------------------------------------|
| 48 48 | 26 | 25 | 21 21 | 19 | 17 | 15 15 |
|---------| | |---------| | |---------|
| 47 47 | 26 | 25 | 20 20 | 19 | 17 | 16 16 |
|-------------------------------------------------|
| 46 | 45 | 27 27 | 29 | 30 | 31 31 | 33 | 34 |
| | |---------| | |---------| | |
| 46 | 45 | 28 28 | 29 | 30 | 32 32 | 33 | 34 |
|-------------------------------------------------|
| 44 44 | 42 | 41 | 39 39 | 38 | 37 | 35 35 |
|---------| | |---------| | |---------|
| 43 43 | 42 | 41 | 40 40 | 38 | 37 | 36 36 |
-------------------------------------------------