Kapitan
Mambeks otrzymał informacje wskazujące na to iż, jego wróg kapitan Mamlaków
przygotowuje się do zaatakowania stolicy kapitana Mambeksa. Kapitan postanowił
przygotować się do obrony. W kosmosie pomiędzy planetami podróżuje się w
jednokierunkowych hipertunelach, może istnieć wiele hipertunali łączących
dwie planety. Kapitan wynajął najlepszego analityka czyli Ciebie do
wyliczenia ilu minimalnie obronnych fortec kosmicznych ( stacjonujących w środku
hipertuneli, jedna forteca na jeden hipertunel ) będzie musiał wynająć
by mieć pewność, że żaden ze statków kosmicznych agresora nie dotarł do
stolicy niezauważony. Kapitan Mamlaków ma ulokowane swoje statki na kilku
planetach i może dotrzeć na planetę Kapitana Mambeksa przez planety na których
nie posiada swoich jednostek. Ataki mogą być przeprowadzone z wielu różnych planet
równocześnie.
Dane wejściowe:
W pierwszym wierszu zapisana jest liczba zestawów danych wejściowych. W kolejnych wierszach jest zapisanych n zestawów danych wejściowych. Każdy zestaw składa się z :
N, M, K: N - liczba planet (<=1000 i >1), M - liczba połączeń jednokierunkowych
hipertuneli (<=10000 i >0), K - liczba planet agresora (<=N i >0). Pierwsza planeta
to planeta Kapitana Mambeksa.
K wartości oznaczające planety agresora (różne od 1)
M linii zawierających opis połączeń planet:
x y - oznaczające połączenie z planety x do planety y (tylko w jedna stronę,
oraz x != y)
Dane wyjściowe
Dla każdego zestawu danych wejściowych program ma wypisać w kolejnych
wierszach:
Minimalną
ilość obronnych fortec kosmicznych które Kapitan będzie musiał wynająć.
Przykładowe dane wejściowe:
1
10 6 3
2 3 5
2 1
2 1
1 2
3 2
8 1
5 6
Przykładowe dane wyjściowe:
2