playlist

Ion este tanar artist si va sustine primul sau spectacol. La spectacol va canta cele n melodii creatie proprie, melodii pe care le-a numerotat de la 1 la n.
El vrea acum sa stabileasca ordinea in care vor fi cantate melodiile.
Stie ca unele melodii cu siguranta nu ar avea acelasi efect asupra publicului daca ar urma una dupa cealalta (ele nu se potrivesc), prin urmare trebuie sa aiba grija la acest aspect cand stabileste ordinea in care vor fi cantate melodiile.
De exemplu daca n=3, dar melodiile 1 si 2 nu se potrivesc, atunci singurele solutii convenabile sunt 1, 3, 2 sau 2, 3, 1.

Cerinta

Scrieti un program care sa determine ordinea in care pot fi cantate cele n melodii, astfel incat sa nu existe melodii consecutive care nu se potrivesc.

Date de intrare

Fisierul de intrare playlist.in contine pe prima linie numarul natural n, care reprezinta numarul de melodii. Pe cea de a doua linie se afla un numar natural m, care reprezinta numarul de perechi de melodii care nu se potrivesc daca sunt cantate una dupa cealalta. Pe fiecare dintre urmatoarele m linii se afla cate doua numere naturale cuprinse intre 1 si n, separate prin cate un spatiu, reprezentand perechile de melodii care nu se potivesc daca sunt cantate una dupa cealalta.

Date de iesire

Fisierul de iesire playlist.out va contine o singura linie pe care vor fi scrise n numere naturale separate prin cate un spatiu, reprezentand melodiile, in ordinea in care vor fi cantate.

Restrictii si precizari

• 1 < n <= 13
• 1 < m <= 30
• Pentru datele de test exista intotdeauna solutie, nu neaparat unica. Daca exista mai multe solutii, va fi afisata prima in ordine lexicografica.

Timp maxim de executie/test: 0.4 secunde

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com