나랏말싸미 America와 different~

한국인 제임스는 외국에서 오래 살아 한글이 서툰 김옥순을 위해 한글을 배우는 게임을 만들었다. 게임은 N x M 표가 주어질 때, (1, 1) 좌표에서 출발하여 (N, M) 좌표까지 이동하면서 가장 짧은 단어를 만드는 것이다. 표에서 이동은 상하좌우 4방향으로 할 수 있다. 이동할 때마다 그 칸에 적힌 자모음을 적고, 적힌 자모음을 순서대로 사용해 하나의 단어를 만들면 된다.

N이 5이고 M이 4인 위 예시를 보면 추매보대, 추우보대 같은 단어를 만들 수 있지만, 가장 짧은 단어의 길이는 3이다. 예를 들어 충남대를 만들 수 있다. 제임스는 김옥순에게 문제를 내기 전에 정답을 알아야 하므로 직접 문제를 풀어 본다.

한글 입출력을 원활하게 하려고 아래 표와 같이 자음과 모음 대신 정수가 주어진다.

글자를 만들 때 자음은 쌍자음이나 겹받침으로 이어 쓸 수 없으며, 모음 두 개도 이어 쓸 수 없다. 문제에서 주어지는 모든 자음은 모든 모음에 대해 초성과 종성으로 사용할 수 있다고 가정한다.

첫 번째 줄에 표의 세로 길이와 가로 길이인 N, M이 주어진다. (4 ≤ N ≤ 50, 4 ≤ M ≤ 50)

두 번째 줄부터 N 줄에 걸쳐 표가 한 행씩 입력된다.

표를 통해 만들 수 있는 가장 짧은 단어의 길이를 출력한다. (N, M) 좌표까지 가서 온전한 단어를 만들지 못하면 "BAD"를 출력한다.