== include(page="template/taskheader" task_id="bal") ==

Poveste şi cerinţă...

Miruna este profesoara la clasa a XII-a D de la Liceul Bunastarii. Clasa a XII-D 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 una dintre fetele scrise de catre el pe biletele?"

h2. Date de intrare

Fişierul de intrare $bal.in$ ...

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$.

h2. Date de ieşire

În fişierul de ieşire $bal.out$ ...

Î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 urmatoarele $N$ linii se vor afisa $N$ numere, $X{~1~}, X{~2~}, ... 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$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 1.000.000$
* Exista posibilitatea ca, din neatentie, un baiat sa dea mai multe biletele cu numele aceleiasi fete.

h2. Exemplu
table(example). |_. bal.in |_. bal.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 6
1 2
1 3
2 1
3 3
4 3
4 4
| DA
2
1
3
4 |
| 4 8
1 2
1 3
2 1
2 4
3 1
3 3
4 3
4 4
| NU

|

h3. Explicaţie
 
...
 
== include(page="template/taskfooter" task_id="bal") ==
 

== include(page="template/taskfooter" task_id="bal") ==

7308