Godzilla
Limit pamięci: 64 MB
Ulubionym zajęciem mieszkańców Bajtołów Dolnych jest namiętne oglądanie popularnego serialu Moda na sukces.
Wszystko za sprawą telewizji kablowej, która dociera ze swoim programem do każdego domu
we wsi. Sieć kablowa składa się z węzłów i jednokierunkowych połączeń. Do każdego węzła sieci
jest podłączony co najmniej jeden dom. Niektóre węzły są wyróżnione i do nich bezpośrednio transmitowany
jest program. W danym domu można go oglądać, jeśli istnieje połączenie (niekoniecznie bezpośrednie)
od wyróżnionego węzła do węzła, do którego podłączony jest dom. Aby zminimalizować koszty,
liczba wyróżnionych węzłów powinna być jak najmniejsza.
Niestety, widmo zagłady zawisło nad Bajtołami! Do wsi przypełzła złośliwa Godzilla, która nie wiedzieć
czemu, żywi się infrastrukturą telewizji kablowej. Co dzień zjada jedno połączenie z sieci.
Ponieważ właściciel telewizji nie może pozwolić sobie na stratę abonentów, jest zmuszony aktualizować
wyróżnione węzły tak, by każdy mieszkaniec mógł oglądać Modę na sukces. Poprosił Cię, byś sprawdził,
czy robi to optymalnie.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i
(), oznaczające liczbę węzłów i połączeń w sieci kablowej.
W kolejnych wierszach znajdują się opisy połączeń. Każdy z wierszy zawiera dwie liczby całkowite
i (), oznaczające
jednokierunkowe połączenie od węzła do węzła .
W kolejnym wierszu znajduje się liczba całkowita () oznaczająca
liczbę zaatakowanych połączeń. Między daną parą wezłów może istnieć co najwyżej jedno bezpośrednie połączenie
w danym kierunku; każde połączenie jest podane na wejściu dokładnie jeden raz.
W kolejnych wierszach znajdują się numery atakowanych połączeń. Połączenia są numerowane od 1
w kolejności występowania na wejściu.
Wyjście
Na standardowe wyjście należy wypisać dokładnie wierszy. Wiersz -ty powinien zawierać
jedną liczbę całkowitą, oznaczającą liczbę wyróżnionych węzłów, do których należy transmitować
Modę na sukces po -tym ataku Godzilli.
Przykład
Dla danych wejściowych:
3 2
1 2
2 3
2
2
1
poprawną odpowiedzią jest:
2
3
Autorzy zadania: Tomasz Idziaszek i Jakub Łącki.