학교 가는 길

점선은 첫 번째 예제에서 Cissi의 최적 경로를 나타낸다.

Cissi는 서쪽에서 동쪽으로 이어지는 긴 도로를 따라 집에서 학교까지 걸어간다. 가는 길에 Cissi는 교차하는 도로가 북쪽으로 뻗은 (N), 남쪽으로 뻗은 (S), 또는 양쪽으로 뻗은 (B) 여러 교차로를 지난다. 모든 교차로에는 교차하는 도로와 주 도로 양쪽에 횡단보도가 있으며(위 그림 참조), Cissi는 횡단보도에서만 도로를 건널 수 있다.

Cissi의 집은 주 도로 북쪽의 가장 서쪽에 있다. 학교는 주 도로 북쪽의 가장 동쪽에 있다. Cissi가 학교로 가는 길에 건너야 하는 도로 수의 최솟값을 계산하도록 돕는 프로그램을 작성한다.

채점

제출한 해답은 여러 테스트 케이스 그룹으로 이루어진 세트에서 평가된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제약 조건

$1$ |$40$| 교차하는 도로가 최대 $20$개이다

$2$ |$60$| 추가 제약 조건이 없다.

입력은 최대 $1\,000$개의 문자로 이루어진 한 줄이며, 각 문자는 N, S, B 중 하나이다. 문자들은 Cissi가 학교로 가는 길에 지나게 될 교차 도로들을 정확히 그 순서대로 나타낸다.

Cissi가 건너야 하는 도로 수의 최솟값인 정수 하나를 한 줄에 출력한다.