Build Gates

Time limit2sMemory limit512 MB

Summary

Count the enclosed regions formed by a walk of up to 1000 unit steps, as each enclosed region needs one gate to reconnect the farm.

Level: Medium6 of 10
Topics: BFS, Graph, Simulation
Solved: No attempts yet

Problem

Farmer John decided to build a new fence around part of his farm. He kept getting distracted while walking, so the fence came out in a much stranger shape than he planned.

John starts at $(0, 0)$ and takes $N$ steps. Each step moves him one unit north, south, east, or west, and behind every step he leaves one unit of fence. If his first step is north, he adds a fence segment from $(0, 0)$ to $(0, 1)$ . He may visit the same point several times, and he may lay a fence on the same segment several times. His path may also cut straight through fence he has already built.

Once the fence is done, John notices that it may have separated parts of the farm from each other, so that walking from one region to another means crossing a fence. He wants to fix this by adding gates. A gate goes on any unit length segment of fence he built, and it lets you pass between the two sides of that segment.

Find the minimum number of gates John needs so that every region of the farm can be reached from every other region.

Input

The first line contains $N$ ( $1 \le N \le 1000$ ).

The second line contains a string of length $N$ describing John's path. Each character is N (north), E (east), S (south), or W (west).

Output

Print one integer, the minimum number of gates John needs to make the whole farm connected again. The answer is 0 when the farm is already connected.

Examples4

Example 1
Input
```
14
NNNESWWWSSEEEE
```
Expected output
```
2
```
Example 2
Input
```
1
N
```
Expected output
```
0
```
Example 3
Input
```
4
NESW
```
Expected output
```
1
```
Example 4
Input
```
2
NS
```
Expected output
```
0
```