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

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?"

Poveste şi cerinţă...

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

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

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

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

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 |

| 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

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

|

h3. Explicaţie
 
...
 

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

7308