Emilian este un ilustru doctor în neurochirurgie, ce tocmai și-a deschis o clinică în orașul Sfîantul 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 a intrării standard 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ă în ziua respectivă. Pe următoarele N linii se află două numere separate printr-un spațiu, reprezentîand preferințele fiecărui pacient.

Date de ieșire

Ieșirea standard va conține 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 afișa NU.

Restricții și precizări

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 2 ∗ N

Exemplu:

Intrare

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

Ieșire

DA
NU

Explicație

Avem T = 2 zile pentru care dorim să determinăm dacă există un program sau nu. îIn 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 diferiț deci răspunsul este NU.