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

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") ==