Se da un arbore cu n noduri si radacina r, apoi q interogari, fiecare cu trei noduri a, b si x. Pentru fiecare interogare, verificati daca x se afla pe drumul simplu dintre 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 trei numere a, b si x.
- Date de iesire
- Pentru fiecare interogare se afiseaza 'DA' daca x se afla pe drumul dintre a si b, altfel 'NU'.
- Restrictii
- 1 <= n <= 100000, 1 <= r <= n, 1 <= q <= 100000
Exemple
Exemplul 1
Intrare
7 1 1 2 1 3 2 4 2 5 3 6 3 7 3 4 7 1 4 7 6 4 7 5
Iesire
DA NU NU
Exemplul 2
Intrare
1 1 1 1 1 1
Iesire
DA