Intr-o tara
indepartata traia Johnie Walker, un personaj caruia ii placeau foarte mult plimbarile.
In tara lui Johnie Walker exista Norase (numerotate de la 1
la N), iar intre anumite perechi
de orase exista poteci. Johnie are dorinta de a umbla pe fiecare poteca din
tara sa. Astfel, el s-a hotarat sa faca o mare plimbare,
desfasurata in mai multe 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, astfel incat 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.
Cerinta
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 sunt scrise doua numere naturale separate
prin spatiu N, reprezentand numarul
de orase si M, reprezentand numarul
de poteci. Pe fiecare dintre urmatoarele M linii sunt scrise cate doua numere naturale
distincte i j (cuprinse intre
1 si N)
cu semnificatia ca exista o poteca de la orasul i
la orasul j.
Date de iesire
Fisierul de iesire johnie.out
va contine pe prima linie un numar natural min
care reprezinta numarul minim de etape ale plimbarii. Urmatoarele min
linii contin drumurile pe care le parcurge Johnie in fiecare etapa, cate un
drum pe o linie. Primul numar de pe linia care descrie un drum reprezinta numarul
de orase parcurse in drumul respectiv, iar urmatoarele numere reprezinta orasele
parcurse, in ordinea parcurgerii. Numerele scrise pe aceeasi linie sunt separate
prin cate un spatiu.
Restrictii si precizari
•1 <= N <= 50000 •1 <= M <= 100000 •Intre doua orase pot exista
mai multe poteci. •O poteca este bidirectionala.
•Nu exista poteci ce incep si se termina in acelasi oras.
Exemplu
johnie.in
johnie.out
7
7 1
2 1
3 1
4 2
3 3
5 4
5 6
7
2 7
1 4 5 3 2 1 3 2
6 7
Daniel
Pasaila
Universitatea "Al.
I Cuza", Iasi - Facultatea
de Informatica
danielpasaila@yahoo.com