Fişierul intrare/ieşire:	amici.in, amici.out	Sursă	Lot Arad 2011
Autor	Cosmin-Mihai Tutunaru	Adăugată de	Gavrila Vlad •GavrilaVlad
Timp execuţie pe test	0.675 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Amici

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

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

Date de intrare

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.

Date de ieşire

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

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.

Exemplu

Cum se trimit solutii?