Informatyka MIMUW

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