Независимое множество

Понятие последовательно-параллельного графа является очень важным в таких разделах, как электротехника, дизайн микросхем, и других. Такие графы используются для задания электрических сетей, сетей передачи данных, и т. п.

В этой задаче граф может содержать параллельные ребра.

Последовательно-параллельные графы определяются рекурсивно следующим образом.

1. Граф из двух вершин s и t, соединенных ребром st, является последовательно-параллельным графом с истоком s и стоком t. Обозначим этот граф как g.
2. Если G₁ является последовательно-параллельным графом с истоком s₁ и стоком t₁, а G₂ является последовательно-параллельным графом с истоком s₂ и стоком t₂, то граф, получаемый объединением вершин t₁ и s₂ в одну, является последовательно-параллельным графом с истоком s₁ и стоком t₂, он обозначается SG₁G₂.
3. Если G₁ является последовательно-параллельным графом с истоком s₁ и стоком t₁, а G₂ является последовательно-параллельным графом с истоком s₂ и стоком t₂, то граф, получаемый объединением вершин s₁ и s₂ в одну (обозначим ее как s₁₂), и объединением вершин t₁ и t₂ в одну (обозначим ее как t₁₂) является последовательно-параллельным графом с истоком s₁₂ и стоком t₁₂, он обозначается PG₁G₂.

Используя приведенное выше определение, мы можем получать разнообразные последовательно-параллельные графы. На рисунке приведен в качестве примера граф SPSgggPgg.

Вам задан последовательно-параллельный граф. Найдите размер максимального независимого множества в нем. Множество вершин называется независимым, если оно не содержит двух вершин, соединенных ребром.

Входные данные

Входной файл INPUT.TXT содержит одну строку описание последовательно-параллельного графа. Описание представляет собой корректное выражение, содержащее только буквы S, P и g. Длина выражения не превышает 10⁵.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число – размер максимального независимого множества в приведенном графе.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!