Trójkolorowe drzewa binarne

Limit pamięci: 32 MB

Drzewo składa się z wierzchołka, do którego podczepiono zero, jedno lub dwa poddrzewa, zwane dziećmi.

Specyfikacją drzewa nazywamy ciąg cyfr. Jeżeli drzewo składa się z wierzchołka, do którego podczepiono:

• zero dzieci, to jego specyfikacja jest ciągiem jednoelementowym, którego jedynym elementem jest cyfra 0;
• jedno dziecko, to jego specyfikacja jest ciągiem rozpoczynającym się od cyfry 1, po której następuje specyfikacja dziecka;
• dwoje dzieci, to jego specyfikacja jest ciągiem rozpoczynającym się od cyfry 2, po której następuje najpierw specyfikacja jednego, a potem drugiego dziecka.

Każdy wierzchołek drzewa trzeba pomalować na czerwono, zielono lub niebiesko. Należy jednak trzymać się dwóch zasad:

• wierzchołek i jego dziecko nie mogą być pomalowane na ten sam kolor,
• jeżeli wierzchołek ma dwoje dzieci, to muszą one być pomalowane różnymi kolorami.

Ile wierzchołków można pomalować na zielono?

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia specyfikację drzewa,
• obliczy maksymalną i minimalną liczbę wierzchołków, które można pomalować na zielono,
• wypisze wyniki na standardowe wyjście.

Wejście

Pierwszy i jedyny wiersz standardowego wejścia zawiera słowo o długości nie przekraczającej 10000 znaków, będącą specyfikacją pewnego drzewa.

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu standardowego wyjścia dokładnie dwie liczby całkowite oddzielone pojedynczym odstępem, odpowiednio maksymalną i minimalną liczbą wierzchołków, które można pomalować na zielono.

Przykład

Dla danych wejściowych:

1122002010

poprawną odpowiedzią jest:

5 2

Autor zadania: Marcin Kubica.