== include(page="template/taskheader" task_id="dans") ==

La concursul naţional de dans din acest an şi-au anunţat prezenţa $N$ dansatori. Deoarece spectacolul este cel mai important la un astfel de eveniment, organizatorii au reuşit să afle (prin mijloace mai mult sau mai puţin ortodoxe) care sunt preferinţele celor N dansatori în materie de parteneri de dans. Prin urmare, ei dispun în acest moment de $M$ perechi de dansatori, dintr-o pereche făcând parte doi dansatori compatibili. Pentru a asigura un spectacol pe cinste, organizatorii vor ca toate aceste perechi să danseze pe ringul de dans. Pentru buna desfăşurare a evenimentului, la un moment dat doar o singură pereche danseaza pe ring (pentru a fi în centrul atenţiei). De asemenea, din motive de eficienţă, în momentul finzalizării unui dans, în ring trebuie să rămână un singur dansator din perechea curentă şi să urce doar un singur alt dansator (cei doi dansatori fiind bineînţeles compatibili). În plus, acelaşi dansator poate dansa maxim două dansuri consecutive (evident, trei dansuri ar fi epuizante).

La concursul naţional de dans din acest an şi-au anunţat prezenţa $N$ dansatori. Deoarece spectacolul este cel mai important la un astfel de eveniment, organizatorii au reuşit să afle (prin mijloace mai mult sau mai puţin ortodoxe) care sunt preferinţele celor N dansatori în materie de parteneri de dans. Prin urmare, ei dispun în acest moment de $M$ perechi de dansatori, dintr-o pereche făcând parte doi dansatori compatibili. Pentru a asigura un spectacol pe cinste, organizatorii vor ca toate aceste perechi să danseze pe ringul de dans, exact o singură dată. Pentru buna desfăşurare a evenimentului, la un moment dat doar o singură pereche danseaza pe ring (pentru a fi în centrul atenţiei). De asemenea, din motive de eficienţă, în momentul finzalizării unui dans, în ring trebuie să rămână un singur dansator din perechea curentă şi să urce doar un singur alt dansator (cei doi dansatori fiind bineînţeles compatibili). În plus, acelaşi dansator poate dansa maxim două dansuri consecutive (evident, trei dansuri ar fi epuizante).

Organizatorii vă roagă să scrieţi un program pentru a programa ordinea celor $M$ dansuri, dacă aceasta este posibilă.
h2. Date de intrare

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$.

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$.

h2. Date de ieşire

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$.

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$.

h2. Restricţii

* $$N$ ≤ $100 000$
* $$N$ ≤ $100 000$$
* $Dacă soluţia nu este unică, se poate afişa oricare.$

* $T$ ≤ $10$
* $3$ ≤ $N$ ≤ $100 000$
* $M$ ≤ $500 000$
* Dacă soluţia nu este unică, se poate afişa oricare.
* Se garantează că perechile din fişierul de intrare sunt distincte două câte două.

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

| 4 5

| 2
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

Perechile dansează în ordinea următoare: (1, 2) (2, 4) (4, 1) (1, 3) (3, 5).

Pentru primul test, perechile dansează în ordinea următoare: (1, 2) (2, 4) (4, 1) (1, 3) (3, 5). Pentru al doilea test, nu exista solutie.

== include(page="template/taskfooter" task_id="dans") ==

9834