격자 도시

인도네시아는 수도를 자카르타에서 칼리만탄의 다른 도시로 옮길 예정이다. 국가 도시 계획가들이 새 도시 계획안을 제시했다. 새 도시는 직사각형 땅 위에 세워지며, 계획안은 땅을 $R \times C$ 격자, 즉 R행 C열의 칸으로 나눈다. 계획가들은 이 격자 설계가 인도네시아의 '현대적'인 모습을 나타낸다고 본다.

각 칸의 중심에는 교차점이 정확히 하나 있다. 이 교차점에 연결되는 도로는 최대 4개다. 도로는 수평 또는 수직 방향으로만 뻗는다. 한 칸이 가질 수 있는 배치는 14가지뿐이다.

• 교차점에 도로가 0개 또는 4개 연결된다(배치 2가지).
• 교차점에 도로가 2개 연결되며 L자 모양이다(배치 4가지).
• 교차점에 도로가 1개 연결된다(배치 4가지).
• 교차점에 도로가 3개 연결된다(배치 4가지).

그런데 계획을 검토해 보니 일부 도로의 끝이 어떤 교차점에도 닿지 않는다. 이런 도로는 두 교차점을 잇지 못하므로 쓸모가 없다. 아래 예시는 $R = 3$, $C = 4$인 경우이며, 삼각형은 끝이 교차점에 있지 않은 도로를 표시한다.

이를 해결하려면 칸을 시계 방향(CW) 또는 반시계 방향(CCW)으로 90도씩 회전하면 된다. 180도 회전하려면 두 번 회전해야 하며, (CW, CW) 또는 (CCW, CCW)로 회전한다. 예시의 오른쪽 그림은 회전을 총 7번 하여 모든 도로가 서로 다른 두 교차점을 잇도록 만든 배치다.

모든 도로가 서로 다른 두 교차점을 잇도록 하는 데 필요한 최소 회전 횟수를 구하라.

첫 줄에 두 정수 $R$과 $C$ ($1 \le R, C \le 30$)가 주어진다. 각각 행의 수와 열의 수다. 이어지는 $R$개의 줄에는 각각 $C$개의 문자열이 주어지며, 한 문자열이 한 칸의 배치를 나타낸다. 문자열은 NESW 형식의 4자리 이진수다. N, E, S, W는 각각 0 또는 1이다. 1은 교차점에서 그 방향으로 도로가 있다는 뜻이고, 0은 도로가 없다는 뜻이다. 1010 배치나 0101 배치는 나타나지 않는다.

모든 도로가 서로 다른 두 교차점을 잇도록 하는 최소 회전 횟수를 한 줄에 출력한다. 불가능하면 -1을 출력한다.