W Bajtocji jest n miast. Miasta są połączone jednokierunkowymi drogami. Każda droga łączy tylko dwa miasta i nie przechodzi przez żadne inne. Niestety, niekoniecznie z każdego miasta da się dojechać do każdego innego. Król Bajtazar postanowił rozwiązać ten problem. Król ma świadomość, że budowanie nowych dróg jest bardzo kosztowne, a budżet Bajtocji nie jest zbyt zasobny. Dlatego też poprosił Cię o pomoc. Trzeba obliczyć minimalną liczbę jednokierunkowych dróg, które trzeba zbudować, żeby z każdego miasta dało się dojechać do każdego innego miasta.
Pierwszy wiersz zawiera dwie liczby całkowite n i m (2 <= n <= 10 000, 0 <= m <= 100 000), oddzielone pojedynczym odstępem i oznaczające, odpowiednio, liczbę miast i liczbę dróg w Bajtocji. Miasta są ponumerowane od 1 do n. W kolejnych m wierszach znajdują się po dwie liczby całkowite oddzielone pojedynczym odstępem. W i+1-szym wierszu znajdują się liczby a_i i b_i (1 <= a_i, b_i <= n dla 1 <= i <= m), reprezentują one jednokierunkową drogę prowadzącą z miasta a_i do b_i.
Pierwszy i jedyny wiersz wyjścia powinien zawierać dokładnie jedną nieujemną liczbę całkowitą - minimalną liczbę dróg, które trzeba zbudować w Bajtocji tak, aby z każdego miasta dało się dojechać do każdego innego miasta.
Dane:
7 11 1 3 3 2 2 1 2 2 3 4 4 5 5 4 3 4 1 6 6 7 7 6
dają odpowiedź:
2
[Zgłoś rozwiązanie] [Moje zgłoszenia]