jungla

Jungla

–	nu vizitează acelaşi trib de mai multe ori (exceptând primul trib, cel de la care pleacă);
–	numărul de triburi vizitate este minim;
–	şi, bineînţeles, pot vizita triburile mergând numai pe drumurile marcate pe hartă şi să revină la poziţia în care îi aşteaptă elicopterul.

Scrieţi un program care să determine o călătorie convenabilă pentru Bill şi John.

h2. Date de intrare

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

Fişierul de intrare jungla.in conţine:
–	pe prima linie două numere naturale N M, separate prin spaţiu, reprezentând numărul de triburi şi respectiv numărul de drumuri directe existente între triburi;
–	fiecare dintre următoarele M linii conţine două numere naturale X Y, separate prin spaţiu, cu semnificaţia “între tribul X şi tribul Y există un drum direct”.

h2. Date de ieşire

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

Fişierul de ieşire jungla.in conţine pe prima linie un număr natural par P, reprezentând numărul de triburi vizitate (minim). Pe cea de a doua linie se află cele P triburi vizitate, scrise în ordinea vizitării, orcare două triburi consecutive fiind separate printr-un spaţiu.

h2. Restricţii

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

* 2 ≤ N ≤ 5000
* 1 ≤ M ≤ 8000
* P > 2
* Pentru datele de test, există întodeauna soluţie, nu neapărat unică.

h2. Exemplu

2 3 5 1
|

h3. Explicaţie
 
...

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