회전하는 머그잔

Lovable의 사무실에는 정말 멋진 커피 머그잔들이 있다. 실제로는 면이 더 많지만, 각 머그잔을 North, West, South, East의 네 면을 가진 단순한 물체로 모델링한다.

앞에 $0$부터 $M-1$까지 번호가 매겨진 $M$개의 머그잔이 있으며, 머그잔을 회전시켜 North 면이 자신을 향하게 해야 한다. 하지만 마법 회전만 수행할 수 있다. 마법 회전은 다음 세 단계로 이루어진다.

• $0 \le a < M$, $0 \le b < M-1$, $a \neq b$을 만족하는 정수 $a$와 $b$를 고른다. $b$은 마지막 인덱스일 수 없음에 유의한다.

• 인덱스 $a$과 $b$에 있는 머그잔을 회전시키지 않고 서로 바꾼다.

• 이제 인덱스 $b$에 있는 머그잔(인덱스 $a$에서 옮겨진 머그잔)과 그 오른쪽 이웃을 가져와 둘 다 $90^\circ$만큼 회전시킨다.

마법 회전에는 머그잔을 서로 바꾸는 단계와 그 후 회전시키는 단계를 포함하여 세 단계가 모두 들어가야 한다는 점에 유의한다.

머그잔을 $90^\circ$만큼 회전시키면 다음과 같이 된다.

• North 면이 자신을 향하던 머그잔은 이제 West 면이 자신을 향한다.

• West 면이 자신을 향하던 머그잔은 이제 South 면이 자신을 향한다.

• South 면이 자신을 향하던 머그잔은 이제 East 면이 자신을 향한다.

• East 면이 자신을 향하던 머그잔은 이제 North 면이 자신을 향한다.

이제 마법 회전만 사용하여 모든 머그잔의 North 면이 자신을 향하도록 배치할 수 있는지 궁금해졌다. 출제자를 감동시키기 위해 마법 회전의 횟수를 최소화하고자 한다.

직접 실험할 만큼 충분한 머그잔이 없다면 Lovable로 만든 이 웹사이트를 사용하여 마법 회전을 시뮬레이션할 수 있다.

채점

해답은 각각 일정한 점수가 배정된 여러 테스트 그룹으로 평가된다. 각 테스트 그룹은 여러 테스트 케이스를 포함한다. 테스트 그룹의 점수를 얻으려면 해당 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$25$| 처음에는 모든 머그잔의 North' 면 또는 East' 면이 자신을 향한다.

$2$ |$35$| $M \leq 100$

$3$ |$40$| 추가 제한 조건이 없다.

첫째 줄에는 앞에 놓인 컵의 수를 나타내는 정수 $M$ ($2 \leq M \leq 5 \cdot 10^5$)이 주어진다.

둘째 줄에는 $M$개의 문자로 이루어진 문자열 $c_1, c_2, \dots, c_M$가 주어진다. $c_i$는 네 문자 `N', `W', `S', `E' 중 하나이며, 현재 $i$-번째 머그잔의 어느 면이 자신을 향하는지를 나타낸다.

모든 머그잔의 North 면이 자신을 향하게 하는 데 필요한 마법 회전의 최소 횟수를 정수로 출력한다. 불가능하다면 -1을 출력한다.

첫 번째 예제에서는 초기 상태가 WW인 두 개의 머그잔으로 시작한다. $a = 1$와 $b = 0$를 반복해서 고르면 머그잔들이 서로 자리를 바꾸고 $90^\circ$만큼 회전한다. 이를 3번 수행하면 머그잔들이 원하는 상태가 된다. 3번보다 적은 움직임으로 이를 달성할 수 있는 마법 회전 수열은 존재하지 않는다.

[h!]

예제 1에 대한 3번의 마법 회전 수열.

두 번째 예제에서는 머그잔들의 상태가 ESE인 채로 시작한다. 다음 두 번의 마법 회전을 수행한다.

• $a = 2$, $b = 1$을 고르면 먼저 머그잔들의 위치가 서로 바뀌어 EES이 된다. 그런 다음 현재 위치 $b = 1$에 있는 머그잔과 그 오른쪽 머그잔을 $90^\circ$만큼 회전시켜 ENE가 된다.

• $a = 0$, $b = 1$을 고르면 먼저 표식이 서로 바뀌어 NEE이 된다. 이제 $b = 1$에 있는 머그잔과 그 오른쪽 머그잔을 회전시키면 NNN가 된다.

2번보다 적은 움직임으로 이를 달성할 수 있는 마법 회전 수열은 존재하지 않는다.

[h!]

예제 2에 대한 2번의 마법 회전 수열.

세 번째 예제에서는 마법 회전을 어떻게 나열해도 모든 머그잔을 회전시켜 머그잔들이 NNNNNN이 되게 할 수 없음이 증명될 수 있다.