Pensje

Limit pamięci: 128 MB

Bajtocka Fabryka Oprogramowania (BFO) zatrudnia pracowników. W hierarchii pracowników każdy ma swojego bezpośredniego przełożonego, z wyjątkiem dyrektora BFO, któremu (pośrednio lub bezpośrednio) podlegają wszyscy pracownicy BFO. Pracownicy mają ustalone miesięczne pensje, przy czym każdy pracownik zarabia inną kwotę, od 1 do bajtalarów. Każdy przełożony zarabia więcej niż każdy z jego podwładnych.

Zgodnie z bajtockim prawem, pensje pracowników na pewnych stanowiskach mogą być publicznie znane. Ponadto, jeśli pensja pewnego pracownika jest publicznie znana, to pensja jego przełożonego także jest znana.

Bajtocki Urząd Podatkowo-Antykorupcyjny (BUPA) postanowił prześwietlić BFO. Zanim BUPA wkroczy z kontrolą do BFO, chce najpierw poznać wysokość pensji wszystkich pracowników BFO, których pensje nie są publicznie znane, ale których wysokość wynika jednoznacznie z publicznie znanych wysokości pensji innych pracowników BFO.

Wejście

W pierwszym wierszu standardowego wejścia podana jest jedna liczba całkowita () oznaczająca liczbę pracowników BFO. Pracownicy są ponumerowani od 1 do .

Kolejne wierszy zawiera informacje o pracownikach. Wiersz o numerze opisuje pracownika numer za pomocą dwóch liczb całkowitych i (, ) oddzielonych pojedynczym odstępem. Liczba to numer bezpośredniego przełożonego pracownika nr . Jeżeli , to jest numerem dyrektora BFO. Jeśli , to jest to wysokość pensji pracownika nr . Jeśli zaś , to wysokość pensji pracownika nr nie jest znana. Dodatnie liczby są parami różne.

Dane wejściowe będą tak skonstruowane, że będzie istniał co najmniej jeden sposób przypisania płac pracownikom zgodny z ich hierarchią.

W testach wartych łącznie 54% punktów zachodzi dodatkowy warunek .

Wyjście

Twój program powinien wypisać na standardowe wyjście wierszy, z których każdy powinien zawierać jedną liczbę całkowitą. Jeżeli pensja pracownika numer jest jawna lub może zostać wywnioskowana na podstawie znanych publicznie pensji innych pracowników, to -ty wiersz wyjścia powinien zawierać pensję pracownika numer . W przeciwnym przypadku -ty wiersz wyjścia powinien zawierać 0.

Przykład

Dla danych wejściowych:

10
2 2
2 10
1 0
2 9
2 5
4 0
6 0
6 0
5 0
5 0

poprawną odpowiedzią jest:

2
10
1
9
5
8
0
0
0
0

Wyjaśnienie do przykładu: Na rysunku liczby w kółkach to numery pracowników, a liczby zapisane kursywą to publicznie znane pensje pracowników. Pracownik nr 3 musi zarabiać 1 bajtalar, a pracownik nr 6 musi zarabiać 8 bajtalarów. Zarobki pracowników nr 7, 8, 9 i 10 nie wynikają jednoznacznie z publicznie znanych zarobków innych pracowników.

Autor zadania: Adam Karczmarz.