Fişierul intrare/ieşire:	maimute.in, maimute.out	Sursă	Lista lui Francu
Autor	Catalin Francu	Adăugată de	Savin Tiberiu •devilkind
Timp execuţie pe test	0.225 sec	Limită de memorie	10240 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Maimute

Odata cu aparitia antidotului impotriva maimutei nebune numarul maimutelor moarte a scazut foarte mult, cunoscandu-se astfel foarte bine arborele genealogic al familiei acestora. Din pacate insa varsta inaintata si-a pus amprenta pe memoria acestora si pe viteza lor de reactie si din cand in cand apar certuri pe tema structurii lor. Motivul certurilor este relatia de descendenta, deoarece unele maimute sunt mai destepte, alte maimute vor sa stie daca sunt sau nu descendenti ai acelei maimute.

Cerinta

Maimutele au scos din biblioteca lor o structura cu arborele genealogic a celor N care fac parte din tribul cu probleme si de asemenea v-au inmanat M intrebari de genul "Exista o relatie ascendent-descendent intre maimuta X si maimuta Y?"

Date de intrare

In fisierul de intrare maimute.in se vor gasi pe prima linie numarele N si M cu semnificatia din enunt. Pe urmatoarele N-1 linii se vor afla cate 2 numere X si Y cu propietarea ca maimuta X este tatal maimutei Y. Pe urmatoarele M linii se vor afla intrebarile maimutelor descrise prin numerele X si Y.

Date de iesire

In fisierul de iesire maimute.out se vor afla M linii. Pe linia i se va afla cuvantul "DA" daca raspunsul la intrebarea i este da, in caz contrar linia i va contine cuvantul "NU"

Restrictii

• $ 1 ≤ N ≤ 100 000 $
• $ 1 ≤ M ≤ 1 000 000 $

Exemplu

table(example). |_. maimute.in |_. maimute.out |
7
6 4
4 7
3 1
2 5
1 2
4 1
6 
4 6 
3 5 
6 7 
7 1 
4 6 
6 4 
|
DA
NU
NU
DA
DA
DA
|

Explicatie

...

Cum se trimit solutii?