Rezolvare PBinfo #4071

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n noduri și un număr L. Să se determine un ciclu elementar de lungime L.

Date de intrare

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

Următoarea linie conține numărul L.

Date de ieşire

Fişierul de ieşire ciclul.out va conține un singur ciclu elementar de lungime L. Acesta va începe și se va termina cu același nod.

Restricţii şi precizări

• 1 ≤ n ≤ 20
• 1 ≤ i , j ≤ n
• 1 ≤ L ≤ n
• pentru toate datele de test, va exista cel puțin un ciclu de lungime L
• lungimea unui ciclu este egală cu numărul de muchii.

Exemplu:

ciclul.in

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

ciclul.out

3 5 4 6 3