Fie un graf neorientat <tex>G=(V, E)</tex> format din *clici disjuncte total interconectate prin lanţuri*. O *clică* este o mulţime de vârfuri <tex>V^{\prime} \subseteq V</tex> cu proprietatea că între fiecare pereche de vârfuri din <tex>V^{\prime}</tex> există o muchie în <tex>E</tex>. Un *lanţ* între nodurile <tex>u</tex> şi <tex>v</tex> este un drum elementar cu extremităţile <tex>u</tex> şi <tex>v</tex>. Toate celelalte noduri ale lanţului sunt distincte şi au gradul 2, adică au exact doi vecini. Pentru graful dat <tex>V = V_c \cup V_2</tex>, unde <tex>V_c</tex> este mulţimea nodurilor clicilor disjuncte (cu gradul mai mare ca 2), iar <tex>V_2</tex> este mulţimea nodurilor cu gradul 2. Clicile disjuncte sunt total interconectate prin lanţuri, dacă lanţurile au extremităţile în <tex>V_c</tex> şi celelalte noduri în <tex>V_2</tex>, iar fiecare nod din <tex>V_c</tex> este extremitatea unui singur lanţ.

!problema/clici?clici.png!

!{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ă.

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.

h2. Date de intrare

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

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ătoarea linie 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.

h2. Date de ieşire

În fişierul de ieşire $clici.out$ ...

În fişierul de ieşire $clici.out$ se tipăreşte pentru fiecare test o singură linie care începe cu numărul exemplului de test, urmat de caracterul $':'$ şi de cuvântul $'nu'$ dacă graful nu conţine un ciclu Hamiltonian sau $'da'$ urmat de $N$ noduri (numere separate prin spaţiu), care constituie ciclul Hamiltonian, dacă acesta există (trebuie să existe o muchie inclusiv între ultimul nod şi primul). Dacă există mai multe soluţii se acceptă oricare din ele.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $3 ≤ N ≤ 1000$
* $1 ≤ M ≤ 100000$
* fişierul de intrare conţine cel mult 20 de teste

h2. Exemplu
table(example). |_. clici.in |_. clici.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6 10
1 2 1 6 2 3 2 5 2 6 3 4 3 5 3 6 4 5 5 6
9  12
1 2 1 9 2 3 2 9 3 4 3 9 4 5 5 6 5 8 6 7 6 8 7 8
0
| 1:da 1 2 3 4 5 6
2:nu

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="clici") ==