Strazi

strazi

== 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 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.

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") ==

2600