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 și precizări

• $1 \leq T \leq 13$
• $3 \leq N \leq 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 \leq 13$.
• Pentru alte $25\%$ din teste $N \leq 300$.

Exemplu

amici.in

2
6 0
7 1
1 2

amici.out

2 5 6 3 1 4
3 4 2 1 6 7 5