O harta este formata din mai multe regiuni de uscat (maluri si insule) legate intre ele prin poduri. Regiunile de uscat sunt numerotate de la 1 la n, iar podurile sunt reprezentate ca muchii neorientate intre doua regiuni (pot exista mai multe poduri intre aceleasi doua regiuni). Graful format este conex.
Un turist doreste sa traverseze toate podurile existente, fiecare exact o data (poate incepe si termina traseul in orice regiune). Daca acest lucru nu este posibil cu podurile existente, se pot construi poduri noi (intre oricare doua regiuni, eventual chiar intre regiuni deja legate).
Determinati numarul minim de poduri noi ce trebuie construite astfel incat sa existe un traseu care sa foloseasca fiecare pod (vechi si nou) exact o data.
- Date de intrare
- Pe prima linie se citesc doua numere intregi n si m, numarul de regiuni si numarul de poduri existente. Pe urmatoarele m linii se citesc cate doua numere intregi u si v, insemnand ca exista un pod intre regiunile u si v.
- Date de iesire
- Se afiseaza un singur numar intreg: numarul minim de poduri noi necesare.
- Restrictii
- 2 <= n <= 12 1 <= m <= 30 1 <= u, v <= n Graful dat este conex.
Exemple
Exemplul 1
Intrare
2 1 1 2
Iesire
0
Exemplul 2
Intrare
3 3 1 2 2 3 1 3
Iesire
0