Jest to ostatnie z grupy laboratoriów poświęconych strukturom danych. Tym razem zadanie dotyczy drzew binarnych.
Uwaga: Jest to nieco inne zadanie niż przed rokiem.
Zadanie PAR (Park Bitowy)
Dostępna pamięć: 128MB.
W Parku Bitowym znajduje się \( \displaystyle n \) polanek ponumerowanych od 1 do \( \displaystyle n \). Niektóre pary polanek są połączone (dwukierunkowymi) ścieżkami. Jak to przystało na park bitowy, układ ścieżek tworzy drzewo binarne, którego korzeniem jest polanka numer 1.
Bajtek i Bajtyna przyszli po szkole pobawić się w parku. Dzieci postanowiły zagrać w następującą grę. Naprzemiennie jedno z dzieci wskazuje numer polanki \( \displaystyle a \) oraz liczbą całkowitą nieujemną \( \displaystyle d \), a zadaniem drugiego z nich jest odnalezienie w parku jakiejś polanki, której odległość
od polanki \( \displaystyle a \) wynosi \( \displaystyle d \). Jeśli takiej polanki nie ma, dziecko musi to określić.
Bajtek chciałby sobie ułatwić grę. Poprosił Cię, żebyś napisał program, który będzie odnajdował polanki określone przez Bajtynę.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita \( \displaystyle n \) ( \( \displaystyle 2 \le n \le 500\,000 \) ), oznaczająca liczbę polanek w Parku Bitowym. Każdy z kolejnych \( \displaystyle n \) wierszy zawiera dwie liczby całkowite \( \displaystyle a_i \) oraz \( \displaystyle b_i \) ( \( \displaystyle a_i,b_i \in \{-1,1,2,\ldots,n\} \) ), oznaczające, że z polanki numer \( \displaystyle i \) prowadzą ścieżki na polanki numer \( \displaystyle a_i \) oraz \( \displaystyle b_i \). Wartość \( \displaystyle -1 \) oznacza, że dana ścieżka nie istnieje. Dane wejściowe zawierają wszystkie krawędzie konieczne do jednoznacznego zbudowania drzewa ukorzenionego w polance numer 1.
W kolejnym wierszu wejścia znajduje się jedna liczba całkowita \( \displaystyle m \) ( \( \displaystyle 1 \le m \le 500\,000 \) ), oznaczająca liczbę poleceń, które Bajtek otrzymał od Bajtyny. Każdy z następnych \( \displaystyle m \) wierszy zawiera dwie liczby całkowite \( \displaystyle a \) oraz \( \displaystyle d \) ( \( \displaystyle 1 \le a\le n \), \( \displaystyle 0 \le d < n \) ).
Wyjście
Twój program powinien wypisać numery polanek stanowiące odpowiedzi na pytania Bajtyny. Jeśli odpowiedzią na dane pytanie jest więcej niż jedna polanka, Twój program powinien wypisać jakąkolwiek z nich. Jeśli polanka wskazana przez Bajtynę nie istnieje, w odpowiednim wierszu należy wypisać liczbę \( \displaystyle -1 \).
Przykład
Dla danych wejściowych:
8
3 4
-1 6
2 5
-1 -1
7 -1
-1 -1
8 -1
-1 -1
6
1 3
1 4
1 5
6 1
6 4
6 5
poprawnym wynikiem jest:
6
8
-1
2
4
8