Se da un arbore cu n noduri si radacina r, apoi q interogari, fiecare cu doua noduri x si y. Pentru fiecare interogare, verificati daca x apartine subarborelui lui y (inclusiv cazul x = y).
- 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 y.
- Date de iesire
- Pentru fiecare interogare se afiseaza 'DA' daca x apartine subarborelui lui y, altfel 'NU'.
- Restrictii
- 1 <= n <= 100000, 1 <= r <= n, 1 <= q <= 100000
Exemple
Exemplul 1
Intrare
6 1 1 2 1 3 2 4 2 5 3 6 3 5 2 6 2 1 1
Iesire
DA NU DA
Exemplul 2
Intrare
1 1 1 1 1
Iesire
DA