파이프

격자 위에서 하는 퍼즐 게임 '파이프'를 생각하자. 게임판은 $R$개의 행과 $C$개의 열로 이루어진 격자이다. 각 칸의 가운데에는 점이 하나 있고, 그 점에서 북(위), 동(오른쪽), 남(아래), 서(왼쪽) 이웃 칸 방향 중 일부(하나도 없을 수도, 전부일 수도 있다)로 선이 뻗어 있다. 단, 한 칸이 곧은 직선 모양이 되는 것은 금지된다. 즉 서로 반대인 두 방향에 모두 선이 있다면, 나머지 두 방향 중 적어도 한 방향에도 선이 있어야 한다.

각 칸은 원하는 만큼 여러 번 $90^\circ$ 회전할 수 있다. 목표는 모든 칸을 적절히 회전시켜서, 어떤 칸이 어떤 방향으로 선을 가지면 그 방향에 이웃 칸이 존재하고 그 이웃 칸도 정반대 방향으로 선을 가지도록 만드는 것이다. 다시 말해, 격자의 각 변은 양쪽 모두에 선이 있거나 양쪽 모두에 선이 없어야 한다. 주어진 게임판을 이렇게 풀 수 있는지 판정하여라.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에는 두 정수 $R$과 $C$가 공백으로 구분되어 주어진다 ($1 \le R, C \le 12$).

이어지는 $R$개의 줄은 게임판의 각 행을 북쪽에서 남쪽 순서로 나타낸다. 각 줄에는 정확히 $C$개의 문자열이 공백으로 구분되어 주어지며, 서쪽에서 동쪽 순서로 그 행의 칸에 대응한다. 각 문자열의 형식은 다음과 같다.

• 문자열이 문자 x 하나뿐이면, 그 칸에는 어떤 이웃 방향으로도 선이 없다.
• 그렇지 않으면, 문자열은 N, E, S, W 중 일부로 이루어지며, 각각 그 칸의 중심에서 북, 동, 남, 서 이웃 방향으로 선이 뻗어 있음을 뜻한다. 같은 문자가 한 문자열에 두 번 나타나는 일은 없다.

입력은 0 0으로 이루어진 줄로 끝난다. 이 줄은 테스트 케이스가 아니며 처리하지 않는다.

각 테스트 케이스마다, 퍼즐에 해가 존재하면 SOLVABLE을, 그렇지 않으면 UNSOLVABLE을 한 줄에 출력한다.