plan

Plan

== include(page="template/taskheader" task_id="plan") ==

Organizatia secreta a cainilor detectivi care conduc lumea a elaborat un plan de securizare al judetului Tinichea. Momentan judetul contine $N$ orase numerotate de la $1$ la $N$ si exista $M$ sosele, prin intermediul unei sosele putandu-se ajunge de la un oras la altul. Conform unui decret dat de presedinte, circulatia pe orice sosea este permisa doar intr-un singur sens. Pentru ca judetul sa fie securizat trebuie ca din orice oras sa se poate ajunge in oricare alt oras circuland doar pe sosele si evident, doar pe sensul in care este permisa circulatia. Din cauza lipsei de fonduri organizatia isi propune sa contruiasca un numar minim de sosele astfel incat judetul sa fie securizat.

Organizatia secreta a cainilor detectivi care conduc lumea a elaborat un plan de securizare a judetului Tinichea. Momentan judetul contine $N$ orase numerotate de la $1$ la $N$ si exista $M$ sosele, prin intermediul unei sosele putandu-se ajunge de la un oras la altul. Conform unui decret dat de presedinte, circulatia pe orice sosea este permisa doar intr-un singur sens. Pentru ca judetul sa fie securizat trebuie ca din orice oras sa se poate ajunge in oricare alt oras circuland doar pe sosele si evident, doar pe sensul in care este permisa circulatia. Din cauza lipsei de fonduri organizatia isi propune sa contruiasca un numar minim de sosele astfel incat judetul sa fie securizat.

h2. Date de intrare

Pe prima linie a fisierului $plan.in$ se afla numerele $N$ si $M$ cu semnificatia din enunt. Pe urmatoarele $M$ linii se afla cate doua numere $x$ si $y$, cu semnificatia ca exista o sosea pe care se poate ajunge din orasul $x$ in orasul $y$.

Pe prima linie a fisierului de intrare $plan.in$ se afla numerele $N$ si $M$ cu semnificatia din enunt. Pe urmatoarele $M$ linii se afla cate doua numere $x$ si $y$, cu semnificatia ca exista o sosea pe care se poate ajunge din orasul $x$ in orasul $y$.

h2. Date de iesire

Pe prima linie a fisierului $plan.out$ se afla un numar natural $MIN$, numarul minim de sosele ce trebuie construite. Pe urmatoarele $MIN$ linii se afla cate doua numere $a$ si $b$, cu semnificatia ca s-a construit o sosea pe care se poate ajunge din orasul $a$ in orasul $b$.

Pe prima linie a fisierului de iesire $plan.out$ se afla un numar natural $MIN$, numarul minim de sosele ce trebuie construite. Pe urmatoarele $MIN$ linii se afla cate doua numere $a$ si $b$, cu semnificatia ca s-a construit o sosea pe care se poate ajunge din orasul $a$ in orasul $b$.

h2. Restrictii
* $1 ≤ N ≤ 255$
* $1 ≤ M ≤ 1500$

* Daca ignoram sensul de circulatie pe sosele (adica daca pe fiecare sosea s-ar putea circula in ambele sensuri) atunci se poate ajunge din orice oras in oricare alt oras

* Daca exista mai multe posibilitati de amplasare a soselor, se poate afisa oricare
* Daca se afiseaza corect numarul minim de sosele ce trebuie construite se obtine 20% din punctaj

h3. Explicatie

Daca se construieste o sosea de la orasul 3 la orasul 1 este posibil sa se ajunge din orice oras in orice oras. O alta solutie posibila ar putea fi construirea unei sosele de la orasul 3 la orasul 2.

Daca se construieste o sosea de la orasul 3 la orasul 1 este posibil sa se ajunga din orice oras in orice oras. O alta solutie posibila ar putea fi construirea unei sosele de la orasul 3 la orasul 2.

== include(page="template/taskfooter" task_id="plan") ==

2102