Description

Farmer John (FJ) plans to build a fence on part of his farm. Because he did not work carefully, after construction the fence ends up with a very strange shape.

Specifically, FJ starts at $(0, 0)$ and walks $N$ steps, each moving one unit (to the east, south, west, or north).

For each step he takes, he leaves behind a unit-length segment of fence. For example, if his first step is north, he builds a unit of fence from $(0, 0)$ to $(0, 1)$.

FJ may visit the same point multiple times, and he may also build the same fence segment multiple times. If his path crosses a segment that has already been built, the fence may have intersections.

Needless to say, FJ is dismayed when he sees the finished fence. In particular, he finds that some regions are enclosed by the fence and therefore cannot be reached. FJ wants to install some gates on the fence to fix this problem.

A gate can be installed on any unit-length fence segment (note: it must be one of the steps he previously took), allowing passage through that segment from one side of the fence to the other.

Compute the minimum number of gates FJ needs to install to guarantee that any region on the farm is reachable from any other region.

Input Format

The first line contains an integer $N$.

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

Output Format

Output a single integer, the minimum number of gates needed to ensure that all regions of the farm are connected.

14
NNNESWWWSSEEEE

2

Hint

Note that if the farm is initially connected, the answer is $0$. Constraints $1\le n\le 1000$.

Translated by ChatGPT 5