== include(page="template/taskheader" task_id="dans") ==
Poveste şi cerinţă...
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$ ...
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
În fişierul de ieşire $dans.out$ ...
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
* $... ≤ ... ≤ ...$
* $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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
...
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") ==
