Diferente pentru problema/dans intre reviziile #13 si #8

Nu exista diferente intre titluri.

Diferente intre continut:

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
* $T$ ≤ $10$
* $3$ ≤ $N$ ≤ $100 000$
* $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 |
| 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
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.
Perechile dansează în ordinea următoare: (1, 2) (2, 4) (4, 1) (1, 3) (3, 5).
== include(page="template/taskfooter" task_id="dans") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

9834