Fişierul intrare/ieşire:grarb.in, grarb.outSursăFMI No Stress 2010
AutorMarius Dumitran, Vlad DutaAdăugată demarius135Dumitran Adrian Marius marius135
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Grarb

Se da un graf G neorientat cu N noduri numerotate de la 1 la N si M muchii. Determinati numarul minim de muchii care trebuie eliminate si numarul minim de muchii care trebuie adaugate in graful G astfel incat acesta sa devina arbore.

Date de intrare

Fişierul de intrare grarb.in contine pe prima linie doua numere naturale N si M reprezentand numarul de noduri respectiv numarul de muchii ale lui G. Pe fiecare din urmatoarele M linii se afla cate doua numere naturale x si y cu semnificatia ca exista o muchie intre nodurile x si y. Intre doua noduri pot exista mai multe muchii si pot exista muchii de la un nod la el insusi.

Date de ieşire

În fişierul de ieşire grarb.out se va afisa pe prima linie numarul minim de muchii ce trebuiesc eliminate, iar pe cea de-a doua linie numarul minim de muchii care trebuie adaugate pentru ca graful G sa fie transformat in arbore.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 200 000

Exemplu

grarb.ingrarb.out
6 5
1 2
1 3
2 4
1 4
5 6
1
1

Explicatii

O solutie posibila este sa se elimine muchia (1,4) si sa se adauge muchia (2,5)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content