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.