Se da un arbore cu n noduri si radacina r, apoi q interogari, fiecare cu un nod x si un numar k. Pentru fiecare interogare, determinati al k-lea stramos al lui x (mergand k pasi catre radacina), sau -1 daca acesta nu exista.
- Date de intrare
- Pe prima linie se citesc n si r. Urmeaza n-1 linii cu cate o muchie. Urmeaza o linie cu q, apoi q linii, fiecare cu doua numere x si k.
- Date de iesire
- Pentru fiecare interogare se afiseaza al k-lea stramos al lui x, sau -1 daca k depaseste adancimea lui x.
- Restrictii
- 1 <= n <= 100000, 1 <= r <= n, 1 <= q <= 100000, 0 <= k <= n
Exemple
Exemplul 1
Intrare
7 1 1 2 1 3 2 4 2 5 3 6 3 7 3 4 1 4 2 4 5
Iesire
2 1 -1
Exemplul 2
Intrare
1 1 1 1 1 0
Iesire
-1