ABC Pharmaceutics şi XYZ Pharmaceutics au finanţat o expediţie ştiinţifică în junglă. În această expediţie a fost explorată o zonă albă de pe harta lumii, un loc unde ″mâna omului n-a pus niciodată piciorul″.
În junglă, exploratorii au găsit N triburi, pe care le-au numerotat 1, 2, ..., N. Unele dintre aceste triburi comunică, prin urmare exploratorii au construit o hartă pe care au marcat poziţia fiecărui trib şi drumurile existente între poziţiile triburilor. Cea mai interesantă descoperire este că aceste triburi au cunoştinţe extraordinare despre cum pot fi folosite pentru tratarea diferitelor boli plantele care cresc în zona lor.
Bill este un angajat al ABC Pharmaceutics, iar John este un angajat al XYZ Pharmaceutics. De curând ei au primit o misiune grea: trebuie să meargă în junglă şi să încheie contracte de colaborare exclusivă între triburi şi firmele lor. În acest scop, ei vor efectua împreună mai multe călătorii.
Pentru prima călătorie ei au la dispoziţie un elicopter care îi va duce în junglă la unul dintre triburi şi îi va aştepta acolo. Pentru a vizita alte triburi, Bill şi John vor călători pe jos, utilizând numai drumurile marcate pe hartă. Bill şi John consideră că prima călătorie este convenabilă dacă respectă următoarele condiţii:
– ei vizitează un număr par de triburi, astfel încât Bill va încheia un contract cu primul trib, John cu cel de al doilea, Bill cu cel de al treilea, etc.
– 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.
Cerinţă
Scrieţi un program care să determine o călătorie convenabilă pentru Bill şi John.
Date de intrare
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”.
Date de ieşire
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.
Restricţii
2 ≤ N ≤ 5000
1 ≤ M ≤ 8000
P > 2
Pentru datele de test, există întodeauna soluţie, nu neapărat unică.