Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | plan.in, plan.out | Sursă | Autumn Warmup 2007, runda 1 |
| Autor | Din Folclor | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Plan
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.
Date de intrare
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.
Date de iesire
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.
Restrictii
- 1 ≤ N ≤ 255
- 1 ≤ M ≤ 1500
- 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
Exemplu
| plan.in | plan.out |
|---|---|
| 3 6 1 2 2 3 2 3 2 1 1 2 1 1 | 1 3 1 |
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.
