미로 만드는 사람들

문제

미로 만드는 사람들(The Maze Makers)은 퍼즐 책을 내는 출판사다. 이 출판사에서 가장 잘 팔리는 시리즈는 미로 책이고, 직사각형 모양의 2차원 미로를 만들어 주는 프로그램을 쓴다. 미로가 지켜야 하는 규칙은 세 가지다.

바깥 벽 가운데 정확히 두 곳이 비어 있고, 그 두 구멍은 서로 다른 두 칸으로 열린다.
어느 한 칸에서 출발해도 나머지 모든 칸에 갈 수 있다.
미로의 두 칸 사이에는 단순 경로가 정확히 하나 있다.

경로는 칸을 차례로 나열한 것으로, 이웃한 두 칸은 벽이 없는 변을 맞대고 있어야 한다. 단순 경로는 같은 칸을 두 번 지나지 않는 경로다.

미로를 만드는 프로그램은 벽과 통로를 16진수 숫자로 적는다. 칸 하나마다 숫자 하나가 붙는다. 숫자를 네 자리 2진수로 적었을 때 1은 벽, 0은 통로를 뜻한다. 네 자리는 칸의 위쪽에서 시작해 시계 방향으로 위, 오른쪽, 아래, 왼쪽 순서다. 예를 들어 B는 2진수로 1011이므로 위가 벽, 오른쪽이 통로, 아래가 벽, 왼쪽이 벽인 칸이다. E는 1110이므로 위와 오른쪽과 아래가 벽이고 왼쪽만 통로다. 8은 1000이므로 위만 벽이고 나머지 세 방향은 모두 통로다. 한 칸에서 다른 칸으로 갈 때는 통로만 지나 위, 아래, 왼쪽, 오른쪽으로 한 칸씩 움직인다.

입력은 언제나 앞뒤가 맞는다. 이웃한 두 칸의 숫자는 그 사이가 벽인지 통로인지를 똑같이 적고, 바깥 벽이 하나 빠진 칸은 정확히 두 개다.

16진수로 적힌 미로 설명을 읽고 그 미로가 규칙을 지키는지 판정하는 프로그램을 작성하라. 문제가 있으면 출력 항목에 적힌 순서대로 가장 먼저 걸리는 것 하나만 보고한다.

입력

입력은 판정할 미로 하나 이상의 설명으로 이루어진다. 각 설명은 미로의 높이 $H$ 와 너비 $W$ 를 나타내는 정수 두 개로 시작한다. $1 \le H \le 50$ , $2 \le W \le 50$ 이다. 이어지는 $H$ 개의 줄에는 각각 16진수 숫자 $W$ 개가 들어 있다. 숫자는 0부터 9까지와 대문자 A부터 F까지를 쓴다. 입력은 0 두 개가 적힌 줄로 끝난다.

출력

미로마다 아래 네 문장 가운데 가장 먼저 해당하는 것 하나를 출력한다.

NO SOLUTION: 바깥 벽에 뚫린 두 구멍 사이를 미로 안쪽으로 잇는 경로가 없다.
UNREACHABLE CELL: 두 구멍 가운데 어느 쪽에서 통로를 따라가도 닿지 못하는 칸이 하나 이상 있다.
MULTIPLE PATHS: 단순 경로가 두 개 이상인 칸 쌍이 있다. 두 단순 경로는 일부라도 다르면 서로 다른 경로로 센다.
MAZE OK: 위의 어느 문제도 없다.

네 문장은 적힌 순서대로 우선순위를 갖는다. 두 구멍 사이에 경로가 없으면서 닿지 못하는 칸도 있으면 NO SOLUTION만 출력한다. 닿지 못하는 칸이 있으면서 단순 경로가 여러 개인 칸 쌍도 있으면 UNREACHABLE CELL을 출력한다.