Blokada

Limit pamięci: 32 MB

Już w zeszłym roku UOB (Urząd Ochrony Bajtocji) dowiedział się o planowanym zamachu na bajtockie łącza internetowe. Długie śledztwo wykazało, że za tym zamachem stoi jedna osoba. Mózgiem całej operacji jest prawdopodobnie pewien informatyk ukrywjący się pod pseudonimem "S**" (nie możemy go całkowicie ujawnić ze względu na dobro śledztwa). Jednakże od kilku miesięcy nie mozna go znaleźć mimo poszukiwań na wielką skalę. Ze zdobytych podczas śledztwa informacji wynika, że celem ataku będzie uniemożliwienie wysyłania komunikatów z serwera do serwera . Wiadomo, że Bajtocki Internet niewiele różni się od tego jaki znamy. Składa się on z serwerów i łączy internetowych pomiędzy nimi. Jednakże bajtockie łącza są jednokierunkowe. Przebiegły informatyk "S**" pozakładał pułapki na łączach. Po aktywacji pułapka przerywa łącze, na którym została założona. Wiadomo, że "S**" zlecił założenie możliwie najmniejszej liczby pułapek, ale w sposób uniemożliwiający komunikację od serwera do serwera . UOB zwraca się do Ciebie (jako najlepszego programisty :-)) z prośbą o pomoc. Chciałby wiedzieć ile pułapek polecił założyć "S**" (jak je znaleźć to już inna historia).

Wejście

Na wejściu znajdują się informacje na temat bajtockiej sieci internetowej. W pierwszej lini są podane liczby i , , oznaczające odpowiednio liczbę serwerów i łączy. Serwery ponumerowane są od 1 do . W następnych wierszach znajdują się opisy łączy. Opis każdego łącza składa się z liczb i , , . Oznaczają one, że istnieje łącze od serwera do serwera . Wiadomo, że pomiędzy dwoma dowolnymi serwerami może istnieć tylko jedno bezpośrednie łącze.

Wyjście

Na wyjściu powinna znaleźć się jedna liczba - minimalna liczba pułapek, które polecił zastawić "S**", żeby przerwać połączenie pomiędzy serwerami 1 i .

Przykład

Dla danych wejściowych:

5 5
1 2
1 3
2 4
3 4
4 5

poprawną odpowiedzią jest:

1