Pipes

Consider a grid puzzle game called Pipes. The board is a grid with $R$ rows and $C$ columns. Each square has a dot in its centre, and lines extend from that dot toward some, none, or all of its north, east, south, and west neighbouring squares, subject to one restriction: a square may not form a straight line. In other words, if two opposite directions both have lines, then at least one of the other two directions must have a line as well.

You may rotate each square by $90^\circ$ as many times as you like. The goal is to rotate the squares so that, whenever a square has a line in some compass direction, there is a neighbour in that direction and that neighbour has a line in the opposite direction. Equivalently, every edge of the grid must have a line on both of its sides or on neither side. Determine whether the given board can be solved.

The input consists of several test cases.

The first line of each test case contains two integers $R$ and $C$, separated by a space ($1 \le R, C \le 12$).

The following $R$ lines describe the rows of the board from north to south. Each line contains exactly $C$ strings separated by spaces, corresponding to the squares of that row from west to east. Each string has the following format:

• If the string is the single character x, the square has no line toward any neighbour.
• Otherwise, the string consists of some of the characters N, E, S, W, indicating that a line extends from the square's centre toward its north, east, south, or west neighbour, respectively. No character appears in a string more than once.

The input is terminated by a line containing 0 0, which is not a test case and must not be processed.

For each test case, output SOLVABLE if the puzzle has a solution, and UNSOLVABLE otherwise, on its own line.