Fișierul intrare/ieșire	network.in, network.out	Sursă	Concurs Shumen juniori 2017
Autor	autor necunoscut	Adăugată de	Spatarel Dan-Constantin • spatarel
Timp de execuție pe test	0.1 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Computer network

O rețea de calculatoare este compusă din N calculatoare, numerotate de la 0 la N – 1. Fiecare calculator, după ce primește un mesaj, îl transmite altor calculatoare cu care este conectat. Dacă un mesaj de la calculatorul X poate ajunge la calculatorul Y nu înseamnă neapărat că și un mesaj de la calculatorul Y poate ajunge la calculatorul X. Administratorii de sistem doresc să determine numărul minim de calculatoare de la care trebuie transmis un mesaj astfel încât mesajul să ajungă la toate calculatoarele din rețea.

Pentru o mai bună transmitere a mesajelor ei consideră că rețeaua trebuie sa fie extinsă prin adăugarea de noi conexiuni între anumite calculatoare, astfel incât atunci când se trimite un mesaj de la un calculator oarecare acest mesaj va fi distribuit tuturor calculatoarelor din rețea. În acest scop, este necesar să se determine numărul minim de conexiuni care trebuie adăugate astfel încât fiecare calculator să poată fi utilizat ca și calculator inițial în distribuirea mesajelor.

Scrieți un program care calculează numărul minim de calculatoare de la care poate fi trimis un mesaj astfel încât acesta să fie distribuit la toate calculatoarele din rețea și care găsește numărul minim de conexiuni ce trebuie adăugate astfel încât un mesaj trimis de la un calculator arbitrar ales sa ajungă la toate celelalte calculatoare din rețea.

Date de intrare

Fișierul de intrare network.in conține pe prima linie două numere întregi N și M, reprezentând numărul de calculatoare și numărul de conexiuni dintre acestea. Fiecare din următoarele M linii descrie o conexiune. Primul număr reprezintă calculatorul care trimite mesajul iar al doilea număr reprezintă calculatorul care primește mesajul.

Date de ieșire

Fișierul de ieșire network.out va conține pe o singură linie, două numere întregi reprezentând numărul minim de calculatoare care pot fi folosite ca și calculatoare inițiale pentru distribuirea unui mesaj către toate calculatoarele din rețea și numărul de conexiuni ce trebuie adăugate la rețea astfel încât fiecare calculator să poată fi utilizat ca și calculator inițial în distribuirea mesajelor.

Restricții

• 2 ≤ N ≤ 1 600
• 0 ≤ M ≤ 120 000

Exemplu