M. Робинзон и крокодилы

На острове размером $n \times m$ спят крокодилы. Каждый крокодил, если его напугать, бежит строго в свою сторону — на север, юг, запад или восток — пока не окажется в воде за краем острова.

Если на пути напуганного крокодила окажется другой крокодил, они столкнутся и нападут на Робинзона. Поэтому пугать можно только того, у кого путь до воды свободен. Крокодилы пугаются по одному: следующий орех летит, только когда предыдущий уже в воде.

Найдите наибольшее количество крокодилов, которых можно прогнать.

Прямое моделирование «пройти по всем и проверить путь» слишком медленно. Заметьте, что путь крокодила свободен ровно тогда, когда в его направлении нет ближайшего крокодила; а когда крокодил уходит, освободиться может только тот, кто смотрел на него. Это очередь, как в обходе в ширину.

Первая строка содержит числа $n$ и $m$ ($1 \le n, m \le 1000$).

Далее идут $n$ строк по $m$ символов: . — пусто, N, S, E, W — крокодил и его направление.

Одно число — наибольшее количество прогнанных крокодилов.