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.