아스널의 벵거는 무리뉴와 EPL 보드게임을 하기로 하였다. EPL 보드게임의 규칙은 다음과 같다.

1. M x N 칸으로 된 직사각형 모양의 보드판이 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

2. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있다. 새로 이동하는 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

무리뉴에게 계속 패한 뱅거는 이번에는 꼭 무리뉴를 이기고 싶어 한다. 뱅거가 무리뉴를 이기기 위해 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 알려주는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.