Se da un graf neorientat conex, cu n noduri si m muchii (trunchiuri de copaci ce leaga direct doua insulite). Se doreste adaugarea unui numar minim de muchii noi astfel incat graful rezultat sa ramana conex chiar daca se elimina (se scufunda) oricare dintre muchiile sale.
O muchie a carei eliminare deconecteaza graful se numeste punte. Cerinta este ca, dupa adaugarea muchiilor noi, graful sa nu mai contina nicio punte.
Determinati numarul minim de muchii noi care trebuie adaugate.
- Date de intrare
- Pe prima linie se citesc doua numere naturale n si m, reprezentand numarul de noduri, respectiv de muchii ale grafului. Pe fiecare dintre urmatoarele m linii se citesc doua numere u si v, reprezentand o muchie intre nodurile u si v. Graful dat este conex, nu contine bucle (muchii de la un nod la el insusi) si nu contine muchii multiple intre aceeasi pereche de noduri.
- Date de iesire
- Se afiseaza, pe o singura linie, numarul minim de muchii care trebuie adaugate.
- Restrictii
- 2 <= n <= 2000 n-1 <= m <= min(n*(n-1)/2, 4000)
Exemple
Exemplul 1
Intrare
5 4 1 2 2 3 3 4 4 5
Iesire
1
Exemplul 2
Intrare
5 4 1 2 1 3 1 4 1 5
Iesire
2