Treebits

Susi și Țuți tocmai au invatat despre arbori in informatica! Aceștia sunt grafuri neorientate conexe aciclice; cu alte cuvinte, un arbore de $N$ noduri are $N-1$ muchii și se poate ajunge din orice nod în oricare alt nod folosind un drum simplu unic. Un drum simplu este un drum care nu parcurge o muchie mai mult de o data.

Deoarece se plictisesc, Susi și Țuți s-au hotarat sa joace un joc pe un arbore cu $N$ noduri, unde fiecarui nod ii poate fi atribuit un pondere si doresc sa satisfaca $Q$ constrangeri de urmatorul tip:

• Susi spune că $AND$-ul pe biti al ponderilor de pe drumul simplu de la nodul $1$ la nodul $K$ este $V$.

Cerință

Se dau $T$ astfel de scenarii. Țuți trebuie să determine pentru fiecare dintre ele daca exista o atribuire a valorilor fiecarui nod in asa fel incat sa fie satisfacute toate constrangerile.

Date de intrare

Pe prima linie se va afla numarul natural $T$, urmat de $T$ scenarii, dupa cum sunt descrise mai jos.

Pe prima linie a scenariului se vor afla numerele naturale $N$ si $Q$, separate prin spatii.

Pe fiecare dintre urmatoarele $N-1$ linii ale scenariului se va afla cate o pereche de numere naturale nenule $a$ si $b$, separate prin spatii, reprezentand o muchie intre nodurile $a$ si $b$.

Pe fiecare dintre urmatoarele $Q$ linii ale scenariului se va afla cate o pereche de numere naturale $K$ si $V$, reprezentand una dintre constrangerile lui Susi.

Date de ieșire

Se va afisa DA sau NU pe o singura linie, pentru fiecare scenariu, in functie de daca exista o atribuire a valorilor fiecarui nod in asa fel incat sa fie satisfacute toate constrangerile.

Restricții și precizări

• $1 \leq T \leq 10$
• $1 \leq N \leq 200\ 000$
• $1 \leq Q \leq 200\ 000$
• $1 \leq K_i \leq N$
• $0 \leq V_i < 2^{31}$
• Definim $AND$-ul intre $A$ si $B$, notat cu $A \& B =$ numarul obtinut din bitii comuni ai lui $A$ si $B$. De exemplu, daca $A = 13 = 1101(2)$ si $B = 11 = 1011(2)$, atunci $A \& B = 1001(2) = 9(2)$.
• Definim drumul simplu dintre nodurile $a$ si $b$ ca fiind succesiunea de noduri $S$, astfel incat $S_1 = a, \dots, S_K = b$, exista muchiile $(S_i, S_{i+1})$ pentru orice $1 \leq i < K$, fiecare muchie este parcursa cel mult o data.
• Daca pe un nod exista doua sau mai multe constrangeri contradictorii, atunci NU exista solutie.
• Scenariile din exemplu sunt separate printr-un newline, dar in teste nu sunt.
• Pentru teste in valoare de $10$ puncte: $N = 2, Q = 2$
• Pentru alte teste in valoare de $10$ puncte: $N \leq 10, Q \leq 1000, V_i < 2$
• Pentru alte teste in valoare de $10$ puncte: Arborele este un lant de forma $1-2- \dots -N$; $N, Q \leq 1.000, V_i < 2$
• Pentru alte teste in valoare de $10$ puncte: Arborele este un lant de forma $1-2- \dots -N$; $N, Q \leq 1000$
• Pentru alte teste in valoare de $10$ puncte: Arborele este un lant de forma $1-2- \dots -N$; $V_i < 2$
• Pentru alte teste in valoare de $10$ puncte: Arborele este un lant de forma $1-2- \dots -N$;
• Pentru alte teste in valoare de $20$ de puncte: $V_i < 2$
• Pentru alte teste in valoare de $20$ de puncte: nicio restrictie suplimentara

Exemplul 1

treebits.in

4

3 2
1 2
2 3
2 5
3 4

6 4
1 2
1 3
3 4
3 5
3 6
1 100
2 96
3 36
4 4

6 4
1 2
1 3
3 4
3 5
3 6
1 100
2 95
3 36
4 4

2 2
1 2
1 0
2 1

treebits.out

DA
DA
NU
NU

Explicație

In primul scenariu, putem atribui nodului $1$ valoarea $13$, nodului $2$ valoarea $5$, iar nodului $3$ valoarea $4$. Atunci, restrictiile $V(1)\ \&\ V(2) = 13\ \&\ 5 = 5$ si $V(1)\ \&\ V(2)\ \&\ V(3) = 13\ \&\ 5\ \&\ 4 = 4$ sunt satisfacute. De asemenea, $V(1)$ ar fi putut lua si valorile $5$, $7$, $9$, $15$, $37$, etc.

In al doilea scenariu, putem atribui nodului $1$ valoarea $100$, nodului $2$ valoarea $96$, nodului $3$ valoarea $36$, nodului $4$ valoarea $4$, nodului $5$ valoarea $1$, iar nodului $6$ valoarea $0$. Atunci, restrictiile $V(1) = 100$, $V(1)\ \&\ V(2) = 100\ \&\ 96 = 96$, $V(1)\ \&\ V(3) = 100\ \&\ 36 = 36$ si $V(1)\ \&\ V(3)\ \&\ V(4) = 100\ \&\ 36\ \&\ 4 = 4$ sunt satisfacute. De asemenea, nodurile $5$ si $6$ pot lua orice valoare.

In al treilea scenariu, nu exista solutie pentru care $100\ \&\ V(2) = 95$.

In al patrulea scenariu, $V(1) = 0$ si $V(1)\ \&\ V(2) = 0\ \&\ V(2) = 1$ nu are solutie.