연아와 연재는 아래 그림과 같은 모양으로 보도블록이 깔린 지역에서 자주 놀곤 한다. 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이 주어질 때 최대 몇 개의 타일을 지날 수 있는지, 그리고 어떤 순서로 타일을 지나야 최대 개수의 타일을 지나게 되는지를 알아내는 프로그램을 작성 하시오.