Please Take My Gift

Wookje is a devoted fan of Gusagwa. Today Wookje wants to deliver a gift to Gusagwa. After several days of observation, Wookje has worked out Gusagwa's movement pattern completely.

The area where Gusagwa lives is a rectangular map of size $N \times M$, divided into square cells of size $1 \times 1$. Gusagwa's position is written as $(i, j)$, which means the cell in the $i$-th row from the top and the $j$-th column from the left.

Each cell of the map holds one of the letters N, W, E, S, and Gusagwa moves according to that letter. When Gusagwa stands on cell $(i, j)$, the letter N teleports Gusagwa to $(i-1, j)$, S to $(i+1, j)$, W to $(i, j-1)$, and E to $(i, j+1)$. Gusagwa never gets tired and keeps moving forever.

Wookje does not know where Gusagwa is right now, so Wookje wants a way to deliver the gift no matter which cell Gusagwa starts from. When Gusagwa arrives at a cell that holds a gift, Gusagwa always takes it. Write a program that finds the minimum number of cells on which gifts must be placed so that Gusagwa always takes a gift, regardless of the starting cell.

The first line contains the height $N$ and the width $M$ of the map. ($1 \le N, M \le 1\,000$, $1 < N \times M \le 1\,000\,000$)

Each of the next $N$ lines contains one row of the map. Each line is a string of length $M$ made only of the letters N, W, E, S.

Following the letters on the map never leads outside the map.

Print on the first line the minimum number of cells on which gifts must be placed.