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