Ewakuacja [A]

Limit pamięci: 32 MB

Wobec narastającego zagrożenia terrorystycznego Agencja Dobrobytu Bajtocji (ADB) postanowiła opracować plan na wypadek ataku. Kluczową dla agencji kwestią jest zagwarantowanie królowi Bajtocji możliwości szybkiej ewakuacji w razie serii zamachów bombowych.

Pałac królewski znajduje się przy jednym ze skrzyżowań w stolicy Bajtocji. Przy innym znajduje się schron, do którego król musi pilnie zostać przewieziony, jeśli tylko wystąpi jakieś zagrożenie. Agencja dysponuje dokładnym planem sieci drogowej stolicy, która to sieć składa się ze skrzyżowań połączonych jednokierunkowymi ulicami.

Droga ewakuacji jest uznawana za szybką, jeśli składa się z co najwyżej trzech ulic. Jeśli atak bombowy odbędzie się na określonej ulicy, staje się ona nieprzejezdna dla królewskiego konwoju. ADB zleciła Ci określenie, na ilu co najmniej ulicach zamachowcy musieliby podłożyć bomby, by król nie miał żadnej szybkiej drogi ewakuacji.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz () oznaczające liczbę skrzyżowań oraz liczbę ulic w stolicy Bajtocji. Skrzyżowania są ponumerowane od do , przy czym pałac królewski znajduje się przy skrzyżowaniu o numerze , a schron przy skrzyżowaniu numer .

W kolejnych wierszach znajduje się opis ulic stolicy Bajtocji. W -tym spośród tych wierszy znajdują się dwie liczby całkowite , (, ) reprezentujące ulicę jednokierunkową biegnącą od skrzyżowania o numerze do skrzyżowania o numerze . Dla każdej uporządkowanej pary skrzyżowań istnieje co najwyżej jedna ulica biegnąca od pierwszego z nich do drugiego.

Wyjście

Twój program powinien wypisać na standardowe wyjście dokładnie jedną liczbę całkowitą - minimalną liczbę ulic, które muszą zaatakować terroryści, by król nie miał żadnej szybkiej drogi ewakuacji.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

2

Wyjaśnienie do przykładu: Aby król nie mógł szybko dojechać do schronu, należy wysadzić ulice oraz (wykreślone na powyższym rysunku).

Autorzy zadania: Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk.