멋진 화살표 나라 대모험

유럽 주니어 정보 올림피아드 2542가 화살표 나라에서 열린다. 화살표 나라는 m개의 행(0부터 m-1까지)과 n개의 열(0부터 n-1까지)로 이루어진 격자 모양이고, 각 칸은 도시를 나타낸다. 행 r, 열 c에 있는 칸을 (r, c)로 표기하자. 참가자들은 (0, 0) 칸에 묵고, 경기장은 (m-1, n-1) 칸에 있다.

화살표 나라의 기묘한 관광 명소는 일부 도시에 있는 거대한 화살표이다. 더 기묘한 점은 이 화살표를 시계 방향으로 90도씩만 돌릴 수 있다는 것이다. 각 화살표는 처음에 북, 동, 남, 서 중 하나를 가리킨다. 주최국의 이름 때문에 EJOI 조직위원회는 이 화살표를 활용하려고 한다.

참가자들은 현재 위치와 상관없이 화살표를 무작정 따라간다. 각 도시에서 화살표가 가리키는 인접한 도시로 그냥 이동한다. 화살표가 없는 도시에 들어가거나 화살표 나라를 벗어나면 그 자리에 머물러 경기장에 영영 도착하지 못한다. EJOI 조직위원회는 참가자들이 묵는 곳인 (0, 0) 칸에서 경기장에 도착하기를 원하므로, 화살표를 몇 개 돌려야 할 수도 있다. 목표를 달성하는 데 필요한 최소 회전 횟수를 구하고, 화살표의 방향과 무관하게 참가자들이 경기장에 도착할 수 없다면 그 사실을 알려주자.

첫째 줄에 행의 수와 열의 수를 나타내는 두 정수 m과 n이 주어진다. 다음 m개의 줄에는 화살표의 초기 방향을 나타내는 n개의 문자가 주어진다(N은 북, E는 동, S는 남, W는 서, X는 이 칸에 화살표가 없음). 마지막 줄의 마지막 문자, 즉 경기장에 해당하는 문자는 X임이 보장된다.

입력 행렬에서 북, 동, 남, 서의 의미는 일반적인 지도에서와 같다. 따라서 문자 N은 위쪽, E는 오른쪽, S는 아래쪽, W는 왼쪽을 뜻한다.

EJOI 조직위원회가 해야 하는 최소 회전 횟수를 출력한다. 불가능하다면 -1을 출력한다.

• 1 ≤ m ≤ 500
• 1 ≤ n ≤ 500
• 각 칸에는 N, E, S, W, X 중 하나의 문자가 들어 있다.