== include(page="template/taskheader" task_id="strazi") ==
Bursuc nu mai scrie poezii, nu mai canta la chitara, nici macar nu mai rezolva probleme de info. Un prieten de-al lui din satul Fribisidi l-a rugat sa-l ajute sa fluidizeze circulatia in sat. In sat exista $N$ case numerotate de la $1$ la $N$ si $M$ poteci pe care se poate circula doar intr-un singur sens. O poteca ce leaga casa $a$ si casa $b$ permite oamenilor sa ajunga de la casa $A$ la casa $B$ (sensul este unic, deci mergand pe aceasta poteca nu se poate ajunge de la casa $B$ la casa $A$). Bursuc mai stie ca nu este posibil ca plecand de la o casa oarecare $A$ si mergand doar pe potecile existente sa se ajunga tot la casa $A$. Cateodata vin oaspeti in sat si acestia ar dori sa viziteze toate casele exact o singura data plimbandu-se numai pe potecile existente. Altfel spus ar dori sa existe o insiruire de case $X{~1~}, X{~2~}, X{~3~} .. X{~N~}$ astfel incat sa existe o poteca intre casele $X{~i~}$ si $X{~i+1~}$ pentru fiecare $i≤N-1$. Momentan acest lucru nu este posibil, de aceea trebuie construite un numar minim de poteci astfel incat sa existe un asemenea drum.
Poveste si cerinta...
h2. Date de intrare
Fisierul de intrare $strazi.in$ contine pe prima linie doua numere $N$ si $M$ avand semnificatia din enunt. Urmeaza $M$ linii care contin cate doua numere $A$ si $B$ cu semnificatia ca exista o poteca de la casa $A$ la casa $B$.
Fisierul de intrare $strazi.in$ ...
h2. Date de iesire
Pe prima linie a fisierului de iesire $strazi.out$ se afla numarul $MIN$ care reprezinta numarul minim de poteci ce trebuie construite. Urmeaza apoi $MIN$ linii, fiecare continand cate doua numere $X$ si $Y$ cu semnificatia ca s-a construit o poteca de la casa $X$ la casa $Y$. Pe ultima linie a fisierului se afla $N$ numere naturale distincte cu valori intre $1$ si $N$, reprezentand un traseu pe care oaspetii l-ar putea urma.
In fisierul de iesire $strazi.out$ ...
h2. Restrictii
* $1 ≤ N ≤ 255$
* $1 ≤ M ≤ 7000$
* Daca exista mai multe solutii posibile, se poate afisa oricare
* Pentru cel putin 20% din teste $N ≤ 10$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. strazi.in |_. strazi.out |
| 3 2
1 2
1 3
| 1
2 3
1 2 3
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
Daca se construieste poteca de la $2$ la $3$ se pot vizita in ordine casele $1$, $2$ si $3$ intre doua case consecutive existand o poteca ce le leaga.
...
== include(page="template/taskfooter" task_id="strazi") ==
