programari

Emilian este un ilustru doctor în neurochirurgie, ce tocmai și-a deschis o clinică în orașul Sfântul Genesius. Deoarece este cunoscut în tot orașul ca fiind cel mai bun neurochirurg din țară, mereu există o mulțime de cereri de la pacienții ce doresc să fie programați la o consultație. Pentru că în mod normal, este foarte ocupat, el lasă secretariatul clinicii să se ocupe de programări. Din păcate, tot personalul secretariatului este plecat în vacanță fix în perioada cea mai aglomerată a anului, și astfel, Emilian vă cere ajutorul pentru a-și programa pacienții.

Într-o zi, el primește cereri de la $N$ pacienți, iar pentru a-i fi mai ușor să își facă programul, Emilian a permis fiecărui pacient să-i propună doar câte două momente de timp în care să poată fi chemat la consult.

Cerința

Știind că personalul lui Emilian este plecat timp de $T$ zile, iar în fiecare zi Emilian are alți pacienți pe care trebuie să îi programeze, ajutați-l să decidă pentru fiecare zi, dacă poate sau nu să programeze toți pacienții din acea zi.

Date de intrare

Pe prima linie se află un număr natural $T$, reprezentând numărul de zile. Apoi pentru fiecare din cele $T$ zile, avem pe prima linie două numere naturale separate printr-un spațiu: $N$, reprezentând numărul de pacienți din acea zi, și $M$, care reprezintă câte momente de timp există in ziua respectivă. Pe următoarele $N$ linii, se află două numere separate printr-un spațiu, reprezentând preferințele fiecărui pacient.

Date de ieșire

Se vor afișa $T$ linii reprezentând răspunsurile pentru cele $T$ zile. Pentru un program realizabil (în care fiecare pacient este programat la unul din cele două momente de timp propuse) se va afișa "DA", iar pentru un program nerealizabil se va avișa "NU".

Restricții și precizări

• $1 \leq T \leq 10$;
• $1 \leq N \leq 100 \ 000$;
• $1 \leq M \leq 2*N$;
• Subtask $1$ ($20$p): $1 \leq N \leq 10$;
• Subtask $2$ ($30$p): $1 \leq N \leq 1 \ 000$;
• Subtask $3$ ($50$p): Fără alte restricții.

Exemplu

stdin

2
3 4
1 3
2 4
3 4
4 3
1 2
2 3
3 1
2 3

stdout

DA
NU

Explicație

Avem $T=2$ zile pentru care dorim să determinăm dacă există un program sau nu. În prima zi putem chema pacientul $1$ la momentul de timp $3$, pacientul $2$ la momentul de timp $2$, iar pacientul $3$ la momentul de timp $4$. Deci răspunsul va fi "DA". Pentru a doua zi, nu putem alege pentru fiecare pacient un moment de timp diferit, deci răspunsul este $NU$.