== include(page="template/taskheader" task_id="johnie") ==
Poveste si cerinta...
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.
h2. 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$.
h2. 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.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $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
h2. Exemplu
table(example). |_. johnie.in |_. johnie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|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
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="johnie") ==
