Rezolvare PBinfo #4636

Cerinţa

Pentru a face LevelUP, Capra din Ohio mai are nevoie de 100XP, de aceea s-a decis sa meargă la școală ca să obține cele 100XP. La ora de informatică, în schimbul a 100XP, are de rezolvat următoarea problemă: Se dă un graf neorientat cu n vârfuri și m muchii. Să se afișeze în ordine lexicografică toate lanțurile hamiltoniene ale grafului dat. Cum habar nu are despre grafuri și lanțuri, vă roagă să o ajutați. Recompensa va fi un video special de mulțumire.

Date de intrare

Fişierul de intrare capradinohio.in conţine pe prima linie numerele n și m, reprezentând numărul de vârfuri ale grafului și numărul de muchii ale grafului. Fiecare dintre următoarele m linii conține câte o pereche de numere i j, cu semnificația că există muchie de la vârful i la vârful j.

Date de ieşire

Fişierul de ieşire capradinohio.out va conține, în ordine lexicografică și pe linii separate, lanțurile hamiltoniene care se pot forma în graful dat. Vărfurile care formează fiecare lanț se separă prin exact un spațiu. Dacă graful nu conține niciun lanț hamiltonian, atunci se va afișa NU EXISTA.

Restricţii şi precizări

• 1 ≤ n ≤ 20
• 1 ≤ m ≤ 100
• 1 ≤ i, j ≤ n
• muchiile se pot repeta în fișierul de intrare

Exemplu:

capradinohio.in

6 8
1 4
1 3
3 5
4 5
2 4
1 2
4 6
3 1

capradinohio.out

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