DEADLINE: 14 ianuarie 1999
TIMP DE IMPLEMENTARE: Maxim o ora (2 ore pentru cei mici)
DOMENIU: Arbori. Problema de tipul "preprocesare + query"

Din nou, scuze celor care o cunoasteti.
Se da un arbore cu radacina cu N noduri. Radacina este intotdeauna
nodul cu numarul 1. Apoi se mai dau M perechi de noduri si se cere sa
se spuna daca ele sunt intr-o relatie de ascendent-descendent, adica
daca unul din ele este sau nu ascendentul (nu neaparat direct) al
celuilalt.

INTRAREA: Fisierul ASC.IN are formatul:
N                  numarul de noduri, N<=5000
X1 Y1
...
X(N-1) Y(N-1)      cele N-1 muchii ale arborelui, in orice ordine si sens
M                  numarul de perechi de testat, M<=1000000 (un milion)
A1 B1
...
AM BM              cele M perechi de noduri care trebuie testate

Observatie: Ai<>Bi si 1<=Ai, Bi<=N pentru fiecare 1<=i<=M.

IESIREA: Fisierul ASC.OUT va contine M linii, pe fiecare linie
aflandu-se cuvantul DA sau NU, dupa cum nodurile din perechea
corespunzatoare se afla sau nu intr-o relatie de dependenta. Punctajul
pentru un test se va acorda numai daca toate raspunsurile acelui test
sunt corecte. De fapt, numai daca fisierul vostru este IDENTIC cu cel
al comisiei. In acest sens, facem precizarea ca ASC.OUT trebuie sa
aiba lungimea de 4*M octeti.

EXEMPLU:
ASC.IN
7
6 4
4 7
3 1
2 5
1 2
4 1
6                       ASC.OUT (24 octeti)
4 6                     DA
3 5                     NU
6 7                     NU
7 1                     DA
4 6                     DA
6 4                     DA

TIMP DE RULARE: Doua secunde pe binecunoscutul Cyrix P200 / 96MB RAM
(S-ar putea sa mai acord ceva timp, nu stiu inca in cat timp scrie al
meu 4MB pe hard-disk)
COMPLEXITATE RECOMANDATA: O(M+N).