Cerinţa

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.

Date de intrare

Fişierul de intrare hamiltonian.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 hamiltonian.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:

hamiltonian.in

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

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