!{width:800px}problema/clici?clici.png!

Fiind dat un graf <tex>G</tex> format din clici disjuncte total interconectate prin lanţuri se cere să se găsească un *ciclu Hamiltonian*, adică un ciclu elementar, care trece prin fiecare vârf al grafului <tex>G</tex> exact o singură dată. Graful din Fig. 1 are ciclul Hamiltonian $1, 2, 3, 4, 5, 6$ iar cel din Fig. 2 nu are ciclu Hamiltonian.

Fiind dat un graf <tex>G</tex> format din clici disjuncte total interconectate prin lanţuri se cere să se găsească un *ciclu Hamiltonian*, adică un ciclu elementar, care trece prin fiecare vârf al grafului <tex>G</tex> exact o singură dată.

h2. Date de intrare

Fişierul de intrare $clici.in$ conţine mai multe teste. Prima linie a testului conţine două numere întregi $N$ şi $M$ separate printr-un spaţiu, reprezentând numărul de noduri şi numărul de muchii ale grafului. Următoarele linii conţin $2M$ numere întregi separate de spaţiu, fiecare pereche de numere consecutive reprezentând o muchie a grafului (vârfurile sunt numere de la $1$ la $N$). Este garantat că fiecare muchie apare o singură dată şi că extremităţile fiecărei muchii sunt distincte. Fişierul se termină cu numărul 0.

Fişierul de intrare $clici.in$ ...

h2. Date de ieşire