Fişierul intrare/ieşire:	bal.in, bal.out	Sursă	Algoritmiada 2012, Runda 3
Autor	Andrei Grigorean	Adăugată de	Andrei Grigorean •wefgef
Timp execuţie pe test	0.5 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Bal

Miruna este profesoara la clasa a XII-a B de la Liceul Bunastarii. Clasa a XII-B este alcatuita din 2 * N elevi, N baieti si N fete. Balul de absolvire se apropie cu pasi repezi, dar perechile inca nu sunt facute. Din cauza ca baietii acestei clase sunt mult prea timizi pentru a invita fetele direct la bal, Miruna i-a cerut fiecaruia sa scrie pe cate un biletel numele aleselor. Dupa ce doamna profesoara colecteaza toate cele M biletele, isi ridica o intrebare existentiala: "Exista mai mult de o modalitate de realiza perechile pentru bal astfel incat fiecare baiat sa danseze cu o fata pe care o place?"

Date de intrare

Fişierul de intrare bal.in va contine pe prima linie numerele N si M, reprezentand numarul de baieti (si de fete) si respectiv numarul de biletele primite. Pe urmatoarele M linii se vor afla perechi de forma A B, cu semnificatia ca baiatului A i-ar face placere ca perechea lui in seara balului sa fie fata B.

Date de ieşire

În fişierul de ieşire bal.out va contine pe prima linie cuvantul DA in cazul in care este posibila exact o singura modalitate de a realiza perechile pentru bal. In acesasta situatie, pe cea de-a doua linie se vor afisa N numere, X₁, X₂, ... X_N, unde X_i inseamna ca baiatul i va fi cuplat cu fata X_i.
In cazul in care nu exista nicio aranjare, sau sunt posibile mai multe aranjari, se va afisa doar cuvantul NU.

Restricţii

• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 1.000.000

Exemplu

Cum se trimit solutii?