W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.
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.
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.
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.