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.