== include(page="template/taskheader" task_id="amici") ==
Poveste şi cerinţă...
În urmă cu foarte mult timp, pe tărâmul Amiciţiei, fiecare persoană avea ca amici toate celelalte persoane. Acum, când invidia este la tot pasul, au apărut divergenţe între persoane. Mai exact, există $N$ persoane numerotate de la $1$ la $N$ şi $M$ perechi de câte două numere reprezentând două persoane care sunt certate. Două persoane se consideră într-o relaţie de amiciţie dacă nu sunt certate.
După o noapte furtunoasă, fiecare dintre cele $N$ persoane vor să se mute în locuinţa unui amic, astfel încât în fiecare locuinţă să se mute exact o persoană. De asemenea, ei nu vor să existe nicio pereche de amici care să facă schimb între ei (dacă $A$ se mută la $B$ atunci şi $B$ să se mute la $A$).
h2. Cerinţă
Dându-se $T$ tărâmuri de tip Amiciţia şi cunoscând pentru fiecare tărâm: $N$ – numărul de persoane şi $M$ – numărul perechilor de persoane certate, să se determine pentru fiecare persoană numărul de ordine al amicului în casa căruia se mută.
h2. Date de intrare
Fişierul de intrare $amici.in$ ...
Fişierul de intrare $amici.in$ conţine pe prima linie numărul $T$, iar pe următoarele linii va fi descris fiecare tărâm în parte. Descrierea fiecărui tărâm începe cu o linie ce conţine $N$ şi $M$, iar pe următoarele $M$ linii se află câte două numere naturale $A$ şi $B$ reprezentând faptul că persoanele $A$ şi $B$ sunt certate.
h2. Date de ieşire
În fişierul de ieşire $amici.out$ ...
Fişierul de ieşire $amici.out$ conţine $T$ linii, câte una pentru fiecare tărâm din fişierul de intrare. Dacă există soluţie, pe linia $i$ se vor afla $N$ numere distincte. Al $k$-lea număr reprezintă amicul în a cărei casă se mută persoana k. Dacă nu există soluţie va fi scris $“-1”$ (ghilimelele sunt pentru claritate).
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 13$
* $3 ≤ N ≤ 1 000$
* Se garantează că o persoană este certată cu mai puţin de jumătate din numărul total de persoane.
* Dacă există mai multe soluţii, se poate afişa oricare.
* Pentru $15%$ din teste $N ≤ 13$.
* Pentru alte $25%$ din teste $N ≤ 300$.
h2. Exemplu
table(example). |_. amici.in |_. amici.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
6 0
7 1
1 2
| 2 5 6 3 1 4
3 4 2 1 6 7 5
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="amici") ==
