Drzewa
Limit pamięci: 32 MB
Pamiętacie Fifusia, który nie znosił informatyki? Obecnie dowódca postawił przed nim bardzo ważne zadanie.
Fifuś ma nadzieję, że jeśli uda mu się je wykonać, to wyrwie się z korpusu szeregowych i zostanie
mianowany kapralem.
Fifuś wraz ze swoim oddziałem jest obecnie na froncie, ukryty w bazie, a na zachód od nich roztacza
się niebezpieczny obszar, na którym mogą znajdować się nieprzyjaciele.
Na obszarze tym znajduje się ponumerowanych drzew (od do ).
Baza, która nie jest drzewem (oznaczona numerem ), położona jest
na wschód w stosunku do innych drzew. Od każdego drzewa wychodzi dokładnie jedna ścieżka w kierunku wschodnim,
która prowadzi do bazy lub do innego drzewa oraz pewna liczba ścieżek w kierunku zachodnim,
które prowadzą do innych drzew. Ponadto z bazy do każdego drzewa da się dojść na dokładnie jeden sposób.
Misja Fifusia rozpocznie się przy pewnym drzewie (lub w bazie) i będzie polegała na
przemieszczaniu się pomiędzy drzewami w kierunku zachodnim tak długo, jak to będzie możliwe.
Każda ścieżka ma określoną trudność, która wyrażana jest za pomocą małych liter alfabetu:
a oznacza najłatwiejszą ścieżkę, z najtrudniejszą.
Fifuś, jak przystało na dzielnego żołnierza, nie stroni od niebezpieczeństwa. Chciałby, aby misja, którą
odbędzie, była najtrudniejszą możliwą. Spośród dwóch misji trudniejsza jest ta, w której trudniejsza
jest pierwsza ścieżka, na której te misje się różnią. Jeśli trudności kolejnych ścieżek w obu misjach
są odpowiednio takie same, to Fifusia interesuje misja, która kończy się przy drzewie o najmniejszym
numerze.
Niestety Fifuś nie wie, gdzie będzie musiał zacząć swoją misję, dlatego dla każdego drzewa (i bazy)
chciałby znać najtrudniejszą misję rozpoczynającą się w danym miejscu.
Twoim zadaniem jest mu pomóc. Musisz się pospieszyć, bo Gogoli jest coraz więcej,
a oddział Fifusia jest w potrzasku.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą
(). W następnych wierszach
znajdują się opisy ścieżek pomiędzy drzewami.
W -tym wierszu znajduje się liczba całkowita () oznaczająca drzewo (lub bazę),
do którego dojedziemy idąc wschodnią ścieżką od drzewa o numerze oraz mała litera alfabetu
oznaczająca trudność tej ścieżki.
W testach wartych około punktów zachodzi dodatkowy warunek , a w testach
wartych około punktów zachodzi .
Wyjście
Na standardowym wyjściu powinno się pojawić liczb całkowitych ,
w oddzielnych wierszach, gdzie oznacza numer drzewa, przy którym kończy się najtrudniejsza
misja rozpoczynająca się przy -tym drzewie (lub bazie).
Jeżeli z wierzchołka nie wychodzi, żadna krawędź w kierunku zachodnim, to należy wypisać .
Przykład
Dla danych wejściowych:
5
1 a
1 a
3 b
3 a
poprawną odpowiedzią jest:
4
0
4
0
0
Autor zadania: Łukasz Jocz.