Se da un arbore cu n noduri si radacina r, apoi q interogari, fiecare cu doua noduri a si b. Pentru fiecare interogare, determinati cel mai apropiat stramos comun al lui a si b.
- 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 a si b.
- Date de iesire
- Pentru fiecare interogare se afiseaza LCA(a, b).
- Restrictii
- 1 <= n <= 5000, 1 <= r <= n, 1 <= q <= 5000
Exemple
Exemplul 1
Intrare
7 1 1 2 1 3 2 4 2 5 3 6 3 7 3 4 5 4 7 6 7
Iesire
2 1 3
Exemplul 2
Intrare
1 1 1 1 1
Iesire
1