Fişierul intrare/ieşire:	johnie.in, johnie.out	Sursă	.campion 2007
Autor	Daniel Pasaila	Adăugată de	Daniel Pasaila •danielp
Timp execuţie pe test	0.1 sec	Limită de memorie	20096 kbytes
Scorul tău	N/A	Dificultate	4/5

Johnie

Intr-o tara indepartata traia Johnie Walker, un personaj caruia ii placeau foarte mult plimbarile. Tara lui era organizata in N orase, iar intre anumite perechi de orase existau poteci. Johnie are dorinta de a umbla pe fiecare poteca din tara sa. Astfel, el s-a hotarat sa faca o mare plimbare intr-un numar de etape. In fiecare etapa Johnie porneste din orice oras din tara, parcurge un anumit drum si se opreste in ce oras doreste. Un drum este reprezentat de un sir de orase, a.i intre oricare 2 orase consecutive din sir exista o poteca. In plimbarea lui, Johnie doreste sa parcurga fiecare poteca o singura data. Lui ii este indiferent daca trece printr-un oras de mai multe ori, chiar in acelasi drum.
Dandu-se numarul de orase din tara si potecile dintre acestea, se cere sa se determine numarul minim de etape in care Johnie poate parcurge toate potecile. De asemenea, se cere si o modalitate de parcurgere a potecilor, pe etape.

Date de intrare

Pe prima linie a fisierului johnie.in este scris numarul N, reprezentand numarul de orase si M, reprezentand numarul de poteci. Pe urmatoarele M linii sunt scrise perechile (i, j) ce marcheaza existenta unei poteci de la orasul i la orasul j.

Date de iesire

Prima linie a fisierului johnie.out trebuie sa contina numarul minim de etape. Urmatoarele linii contin, cate unul pe linie, drumurile pe care le parcurge Johnie in fiecare etapa. Primul numar dintr-o anumita linie reprezinta numarul de orase parcurse in drumul respectiv, iar urmatoarele numere reprezinta orasele parcurse, in ordine.