Zamek

Treść

Grupa zapalonych graczy komputerowych znanych jako Rycerze Optycznej Myszki już od wielu lat spotyka się na sesjach, przez wtajemniczonych zwanych wgrygraniem. Podczas tychże sesji Rycerze podbijają kolejne światy zmagając się z niezliczonymi smokami, hordami dzikich barbarzyńców, zaklęciami czarnoksiężników i innymi przeszkodami, by w końcu w glorii i chwale dotrzeć do celu.

Tytułowy Zamek już od kilku dni spędza graczom sen z powiek. Celem gry jest uwolnienie księżniczek, które okrutny czarnoksiężnik Waks porwał i uwięził w mrocznym zamczysku Meldor. Po wielu godzinach boju ze strażnikami Rycerzom udało się zdobyć kompletną mapę twierdzy. Na mapie naniesione są wszystkie przejścia i komnaty z zaznaczeniem tych, w których Waks uwięził księżniczki. Każde z przejść jest jednokierunkowe. Co więcej, pomiędzy dwiema komnatami może istnieć wiele przejść. Istnieją też przejścia, które rozpoczynają się i kończą w tej samej komnacie.

Dzięki zaklęciu teleportacji Rycerze mogą całą grupą przenieść się do dowolnej komnaty, z której będą rozpoczynać swoją wędrówkę po zamku, każdy w poszukiwaniu swojej wybranki. Niestety, po dokładnej analizie mapy okazało się, że nie z każdej komnaty startowej można dotrzeć do wszystkich księżniczek. Pomóż graczom odnaleźć te komnaty, z których będzie to możliwe.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

W pierwszym wierszu zestawu danych znajdują się dwie liczby całkowite n i m (1<=n,m<=10000), oddzielone pojedynczą spacją, oznaczające odpowiednio liczbę komnat i liczbę przejść w zamku. Kolejne m wierszy zawiera opis przejść. Opis jednego przejścia składa się z dwóch liczb całkowitych p_i i k_i (1<=p_i,k_i<=n), oddzielonych pojedynczą spacją. Liczba p_i to numer komnaty będącej początkiem przejścia, a k_i to komnata będąca jego końcem. Kolejny wiersz, następujący po opisach przejść, zawiera liczbę księżniczek k&nonesep;s (1<=ks<=20) uwięzionych w zamku. Ostatni wiersz zestawu zawiera ks liczb całkowitych kk_j (1<=kk_j<=n), oddzielonych pojedynczymi spacjami, oznaczających numery komnat, w których przetrzymywane są księżniczki. Można założyć, że w żadnej z komnat nie przebywa więcej niż jedna księżniczka.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest liczba komnat, z których można się dostać do każdej z księżniczek uwięzionych w zamku.

Przykład

dane wejściowe:
2
5 6
2 1
5 1
3 1
3 4
4 5
4 3
2
1 5
3 2
2 3
2 1
2
3 1

wynik:
3
1