== 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. 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 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$ ...
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
* $... ≤ ... ≤ ...$
* $ $N$ ≤ $100 000$ $
* $ $N$ ≤ $100 000$ $
* $ Dacă soluţia nu este unică, se poate afişa oricare. $
h2. Exemplu
table(example). |_. dans.in |_. dans.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 5
1 2
4 2
3 5
1 3
4 1
| DA
1 2 4 1 3 5
|
h3. Explicaţie
...
Perechile dansează în ordinea următoare: (1, 2) (2, 4) (4, 1) (1, 3) (3, 5).
== include(page="template/taskfooter" task_id="dans") ==
