h2. Date de intrare

Fişierul de intrare $dans.in$ conţine pe prima linie $T$, reprezentând numărul de teste. Urmează apoi $T$ teste, fiecare fiind structurat după cum urmează: pe prima linie a fiecărui test se află numerele $N$ şi $M$. Pe următoarele $M$ linii se găsesc perechi de numere de forma $x$ $y$, cu semnificaţia că dansatorul $x$ este compatibil cu dansatorul $y$.

Fişierul de intrare $dans.in$ conţine pe prima linie numerele $N$ şi $M$. Pe următoarele $M$ linii se găsesc perechi de numere de forma $x$ $y$, cu semnificaţia că dansatorul $x$ este compatibil cu dansatorul $y$.

h2. Date de ieşire

Fişierul de ieşire $dans.out$ va conţine rezultatele testelor din fişierul de intrare, fiecare pe linii separate. Pentru fiecare test se procedează după cum urmează: dacă există soluţie pentru testul respectiv, veţi afişa pe o linie textul $DA$, iar pe cea de-a doua linie $M+1$ numere, reprezentând ordinea în care dansatorii urcă pe ring. În caz contrar, pentru testul respectiv, veţi afişa o singură linie cu textul $NU$.

Dacă există soluţie pentru programarea dansurilor respectând condiţiile impuse, în fişierul de ieşire $dans.out$ veţi afişa pe prima linie textul $DA$, iar pe cea de-a doua linie $M+1$ numere, reprezentând ordinea în care dansatorii urcă pe ring. În caz contrar, fişierul de ieşire va conţine textul $NU$.

h2. Restricţii

h2. Exemplu
table(example). |_. dans.in |_. dans.out |

| 2
5 5

| 5 5

  1 2
  4 2
  3 5
  1 3
  4 1

4 3
1 2
1 3
1 4

| DA
  1 2 4 1 3 5

  NU

|
h3. Explicaţie