Labirynt studni

Limit pamięci: 32 MB

Wewnątrz Bajtogóry znajduje się mityczny labirynt studni. Wejście do labiryntu znajduje się na szczycie góry. Labirynt składa się z wielu komnat. Każda z nich jest w jednym z trzech kolorów: czerwonym, zielonym lub niebieskim. Dwie komnaty tego samego koloru wyglądają identycznie i są nieodróżnialne. W każdej komnacie znajdują się trzy studnie oznaczone numerami 1, 2 i 3. Między komnatami można poruszać się tylko w jeden sposób - wskakując do jednej ze studni spada się (niekoniecznie pionowo) do jednej z komnat położonych niżej. Z komnaty, w której znajduje się wejście do labiryntu można przedostać się w ten sposób do każdej z pozostałych komnat. Wszystkie drogi przez labirynt prowadzą do smoczej jamy znajdującej się na samym jego dnie. Każdemu przejściu przez labirynt odpowiada ciąg numerów studni wybieranych w kolejno odwiedzanych komnatach. Ciąg ten nazywa się planem podróży.

W smoczej jamie żyje Bajtosmok. Legenda głosi, że ten, kto przedstawi Bajtosmokowi dokładny plan labiryntu, otrzyma wielkie skarby. Wszystkich innych Bajtosmok potężnym kopnięciem wyprasza z wnętrza góry.

Śmiałek o imieniu Bajtazar wielokrotnie przemierzał labirynt i opracował jego mapę. Jednak Bajtosmok orzekł, że co prawda wszystkie komnaty znajdują się na mapie, ale wiele komnat jest na niej powtórzonych.

- Ja też - powiedział poklepując Bajtazara po ramieniu - projektując labirynt narysowałem podobny rysunek, ale szybko stwierdziłem, że komnat można zrobić o wiele mniej, a gość poruszający się według dowolnego planu podróży i tak będzie oglądał takie same sekwencje komnat. Pomyślałem trochę i maksymalnie zredukowałem projekt.

Zadanie

Napisz program, który:

• wczyta mapę Bajtazara ze standardowego wejścia,
• obliczy prawdziwą liczbę komnat w labiryncie,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia zapisana jest jedna liczba całkowita , , będąca liczbą komnat (łącznie ze smoczą jamą). Komnaty są ponumerowane od 1 do tak, że komnaty o większych numerach znajdują się niżej (komnata, w której znajduje się wejście do labiryntu ma numer 1, a smocza jama ma numer ). W kolejnych wierszach pliku są opisane komnaty (poza smoczą jamą) oraz studnie prowadzące od nich w dół. W każdym z tych wierszy znajduje się litera, po niej jeden znak odstępu, a następnie trzy liczby całkowite oddzielone pojedynczymi odstępami. Litera oznacza kolor komnaty (C - czerwony, Z - zielony, N - niebieski), a -ta liczba (dla ) jest numerem komnaty, do której prowadzi -ta studnia.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia powinna znaleźć się dokładnie jedna liczba całkowita będąca minimalną liczbą komnat w labiryncie (łącznie ze smoczą jamą), przy której podróżnik poruszający się według dowolnego planu obserwuje taką samą sekwencję komnat, jak dla labiryntu opisanego w pliku wejściowym.

Przykład

Dla danych wejściowych:

11
N 3 5 2
Z 4 5 6
N 7 11 9
N 8 11 10
C 11 9 9
Z 11 9 10
C 11 11 11
C 11 11 11
Z 11 11 11
Z 11 11 11

poprawną odpowiedzią jest:

8

Autor zadania: Marcin Kubica.