maimute

Maimute

== include(page="template/taskheader" task_id="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.

Odata cu aparitia antidotului impotriva maimutei nebune rata mortalitatii a scazut foarte mult printre maimute, 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 arborelui genealogic. Motivul certurilor este relatia de descendenta, deoarece unele maimute sunt mai destepte, alte maimute vor sa stie daca sunt sau nu descendenti ale acelor maimute.

h2. Cerinta

Maimutele au scos din biblioteca lor o structura cu arborele genealogic a celor $N$ maimute 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$?". Dvs trebuie sa raspunzi cat mai repede la aceste intrebari altfel maimutele vor incepe sa se bata iar violenta nu duce la nimic bun :).

Maimutele au scos din biblioteca lor un document vechi cu arborele genealogic a celor $N$ maimute 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$?". Tu trebuie sa raspunzi cat mai repede la aceste intrebari altfel maimutele vor incepe sa se incaiere iar violenta nu duce la nimic bun :).

h2. 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$ reprezentand faptul ca intre maimuta $X$ si $Y$ exista o relatie directa.

In fisierul de intrare $maimute.in$ se vor gasi pe prima linie numarul $N$ cu semnificatia din enunt. Pe urmatoarele $N-1$ linii se vor afla cate 2 numere $X$ si $Y$ reprezentand faptul ca intre maimuta $X$ si $Y$ exista o relatie directa. Pe linia $N+1$ se va afla numarul $M$ cu semnificatia din enunt. Pe urmatoarele $M$ linii se vor afla intrebarile maimutelor descrise prin doua numere $X$ si $Y$.

h2. Date de iesire

h2. Restrictii
* $1$ ≤ $N$ ≤ $100 000$

* $1$ ≤ $M$ ≤ $1 000 000$

* $1$ ≤ $M$ ≤ $500 000$

* Maimuta $1$ este maimuta cea mai batrana si cea mai inteleapta din tot tribul, toate celelalte maimute fiind descendente ale acesteia.
* Relatia ascendent-descendent nu este neaparat directa (vezi exemplu)

DA
DA|

h3. Explicatie
 
...

== include(page="template/taskfooter" task_id="maimute") ==

1893