고양이 몰이

도시에 길고양이가 잔뜩 풀려났습니다. 도시 고양이 포획관인 여러분은 모든 고양이를 붙잡는 중요한 임무를 맡았습니다. 여러분이 만든 최신 발명품인 고양이 덫은, 도시의 한 정사각형 칸에 들어오는 고양이라면 반드시 붙잡아 줍니다.

다행히 세계 최고의 고양이 심리학자가 도와줍니다. 이 전문가는 도시의 어떤 정사각형 칸을 보든, 그 칸에 있는 고양이가 동서남북 네 방향 중 정확히 어느 쪽으로 움직일지 예측할 수 있습니다. 하지만 지금 고양이들이 각각 어느 칸에 있는지는 알 수 없습니다.

정리하면, 도시는 $n \times m$ 격자이고 각 칸에는 정해진 방향이 있습니다. 어떤 칸에 있는 고양이는 그 칸의 방향을 따라 이웃한 칸으로 한 칸 이동하며, 고양이는 절대 도시를 벗어나지 않습니다. 덫을 놓은 칸에 들어오는 고양이는 모두 붙잡힙니다. 고양이가 어느 칸에서 출발하든 반드시 붙잡히도록 보장하면서, 사용하는 덫의 개수를 최소로 하세요.

첫 줄에는 공백으로 구분된 두 정수 $n$과 $m$이 주어집니다 ($1 \le n, m \le 1000$). 도시는 정사각형 칸으로 이루어진 $n \times m$ 격자입니다.

이어지는 $n$개의 줄에는 각각 길이 $m$인 문자열이 주어지며, 각 문자는 'N', 'E', 'S', 'W' 중 하나로 각각 북, 동, 남, 서를 뜻합니다. 첫 줄의 첫 문자가 가장 북서쪽 칸입니다(행은 아래로 갈수록 남쪽, 열은 오른쪽으로 갈수록 동쪽). 각 칸의 문자는 그 칸에 있는 고양이가 움직일 방향입니다. 고양이는 도시를 벗어나지 않으므로, 어떤 방향도 격자 바깥을 가리키지 않습니다.

고양이가 어느 칸에서 출발하더라도 모두 붙잡기 위해 필요한 덫의 최소 개수를 정수 하나로 출력하세요.