Fişierul intrare/ieşire:plan.in, plan.outSursăAutumn Warmup 2007, runda 1
AutorDin FolclorAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.025 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 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

Exemplu

plan.inplan.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 ajunga din orice oras in orice oras. O alta solutie posibila ar putea fi construirea unei sosele de la orasul 3 la orasul 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content