Fişierul intrare/ieşire:bal.in, bal.outSursăAlgoritmiada 2012, Runda 3
AutorAndrei GrigoreanAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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

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 urmatoarele N linii se vor afisa N numere, X1, X2, ... XN, unde Xi inseamna ca baiatul i va fi cuplat cu fata Xi.
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
  • Exista posibilitatea ca, din neatentie, un baiat sa dea mai multe biletele cu numele aceleiasi fete.

Exemplu

bal.inbal.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content