== include(page="template/taskheader" task_id="strazi") ==
Poveste si cerinta...
Bursuc nu mai scrie poezii, nu mai canta la chitara, nici macar nu mai rezolva probleme de info si de aceea va roaga pe voi sa-l ajutati cu urmatoarea problema. Un prieten de-al lui din satul Fribsd l-a rugat sa-l ajute sa fluidizeze circulatia din 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 momentan 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 poteci. 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.
h2. Date de intrare
Fisierul de intrare $strazi.in$ ...
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$.
h2. Date de iesire
In fisierul de iesire $strazi.out$ ...
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.
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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 2
1 2
1 3
| 1
2 3
1 2 3
|
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") ==
