직병렬 주차장

아드리아해 연안과 섬에는 크기와 모양이 제각각인 해변이 늘어서 있는데, 차로 갈 수 없는 곳이 많다. 늘어나는 수요를 감당하려고 해안 근처의 넓은 벌판을 주차장으로 바꿨다. 설계에 참여한 건축가가 모두 전기공학 출신이라 주차장 구조는 회로를 설계할 때 쓰는 직병렬 그래프를 닮았다.

주차장은 주차 공간과 그 공간을 잇는 양방향 도로로 이루어진다. 도로 하나는 서로 다른 주차 공간 두 개를 잇고, 두 주차 공간을 잇는 도로는 많아야 하나다. 한 주차 공간에는 차를 한 대만 세울 수 있고, 차가 서 있는 공간은 다른 차가 지나갈 수 없다.

직병렬 주차장, 줄여서 splot은 소스와 터미널이라고 부르는 주차 공간 두 개를 따로 정해 둔 주차장이며, 주차 공간 하나에서 시작해 직렬 합성과 병렬 합성으로 만든다. splot은 인코딩으로 나타낸다. 인코딩은 구조와 주차 상태를 함께 적은 문자열이다. splot과 그 인코딩은 다음과 같이 재귀적으로 정의한다.

• 주차 공간 하나로만 이루어지고 도로가 없는 주차장은 splot이다. 이 공간이 소스이면서 터미널이다. 인코딩은 공간이 비어 있으면 소문자 o, 차가 서 있으면 소문자 x다.
• $G_1$과 $G_2$가 splot이면 두 splot의 직렬 합성 $G$도 splot이다. 직렬 합성은 $G_1$의 터미널과 $G_2$의 소스 사이에 도로를 놓아 만든다. $G$의 소스는 $G_1$의 소스이고, $G$의 터미널은 $G_2$의 터미널이다. $G_1$과 $G_2$의 인코딩을 각각 $E_1$, $E_2$라고 하면 $G$의 인코딩은 S와 $E_1$, $E_2$, #을 순서대로 이어 붙인 문자열이다.
• $G_1$과 $G_2$가 splot이면 두 splot의 병렬 합성 $G$도 splot이다. 병렬 합성은 새 주차 공간 $s$와 $t$를 만든 다음, $s$를 $G_1$의 소스와 $G_2$의 소스에 각각 도로로 잇고, $t$를 $G_1$의 터미널과 $G_2$의 터미널에 각각 도로로 이어 만든다. $G$의 소스는 새로 만든 $s$이고, 터미널은 새로 만든 $t$다. $s$와 $t$의 한 글자 인코딩을 각각 $E_s$, $E_t$라고 하자. 공간이 비어 있으면 o, 차가 서 있으면 x다. 이때 $G$의 인코딩은 P와 $E_s$, |, $E_1$, $E_2$, |, $E_t$, #을 순서대로 이어 붙인 문자열이다.

splot 인코딩에 들어 있는 소문자의 개수는 그 splot의 주차 공간 개수와 같고, 소문자와 주차 공간은 하나씩 대응된다.

주차장 출구는 하나뿐이고 전체 splot의 소스와 바로 이어져 있다. 어떤 차가 도로와 빈 주차 공간만 지나 소스까지 갈 수 있으면 그 차는 막히지 않았다고 한다. 예를 들어 Sox#는 주차 공간 두 개를 도로 하나로 이은 splot이고, 두 번째 공간에 차가 한 대 서 있다. 이 차는 첫 번째 공간을 지나 출구까지 갈 수 있으므로 막히지 않았다. 여기서 첫 번째 공간에도 차를 세우면 인코딩이 Sxx#가 되고, 두 번째 차는 빠져나갈 길이 없어 막힌다. 전체 splot의 소스에도 차를 세울 수 있지만, 그러면 주차장에 있는 나머지 차가 모두 막힌다.

주차장 운영자는 들어오는 차를 어느 차도 막히지 않게 세우려고 한다. 차가 이미 몇 대 서 있고 그중 막힌 차는 없는 splot이 주어진다. 이미 서 있는 차를 그대로 두고 어떤 차도 막히지 않게 하면서 세울 수 있는 차의 최대 대수를 구하는 프로그램을 작성하시오. 이미 서 있는 차도 대수에 포함한다.

첫째 줄에 splot의 인코딩이 주어진다. 길이는 1 이상 100,000 이하이고, 대문자 P와 S, 소문자 o와 x, 문자 #(ASCII 35), 문자 |(ASCII 124)로만 이루어진다. 입력은 위 규칙에 따라 만든 splot의 인코딩이며, 이미 서 있는 차 중에 막힌 차는 없다.

첫째 줄에 어떤 차도 막히지 않게 하면서 주어진 splot에 세울 수 있는 차의 최대 대수를 정수 하나로 출력한다.