The Maze Makers

The Maze Makers is a publisher of puzzle books. Its best selling series is a line of maze books, and the company runs a program that generates rectangular two dimensional mazes. A maze obeys three rules.

1. Exactly two exterior cell walls are missing, and the two openings lead into two distinct terminal cells.
2. Starting from any one cell, every other cell is reachable.
3. Between any two cells there is exactly one simple path.

A path is a sequence of cells in which each cell and its successor share an edge with no wall on it. A simple path never repeats a cell.

The program writes the walls and passages as hexadecimal digits, one digit per cell. In the four digit binary form of a digit, a 1 is a wall and a 0 is a passage. The four digits start at the top of the cell and run clockwise: top, right, bottom, left. For example, B is 1011 in binary, so the cell has a wall on top, a passage on the right, a wall at the bottom and a wall on the left. E is 1110, so the cell has walls on top, on the right and at the bottom, and a passage only on the left. The digit 8 is 1000, so the cell has a wall only on top. A move goes one cell up, down, left or right, through passages only.

Every input is self consistent. The digits of two neighboring cells agree on whether a wall or a passage sits between them, and exactly two cells are each missing one exterior wall.

Write a program that reads the hexadecimal description of a candidate maze and decides whether it is legitimate. If something is wrong, report only the first problem in the order listed in the output section.

The input holds the descriptions of one or more candidate mazes. Each description starts with two integers $H$ and $W$, the height and the width of the maze, with $1 \le H \le 50$ and $2 \le W \le 50$. The next $H$ lines each hold $W$ hexadecimal digits, written with 0 to 9 and uppercase A to F. The input ends with a line holding a pair of zeros.

For each candidate maze print the first of the following statements that applies.

• NO SOLUTION: there is no path through the interior of the maze between the two exterior openings.
• UNREACHABLE CELL: at least one cell cannot be reached by following passages from either of the two exterior openings.
• MULTIPLE PATHS: some pair of cells has more than one simple path between them. Two simple paths count as distinct if any part of them differs.
• MAZE OK: none of the problems above is present.

The four statements are listed in priority order. If there is no path between the two openings and the maze also has an unreachable cell, print only NO SOLUTION. If the maze has an unreachable cell and also a pair of cells joined by several simple paths, print UNREACHABLE CELL.