Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-04-25 15:18:49.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:dans.in, dans.outSursăONIS 2014, Runda 4
AutorFlorian MarcuAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test1.5 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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, 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ă.

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.

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.

Restricţii

  • N100 000
  • M500 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ă.

Exemplu

dans.indans.out
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

Explicaţie

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?