Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTWPZ078 - PTwPZ Zamek

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 pi i ki (1<=pi,ki<=n), oddzielonych pojedynczą spacją. Liczba pi to numer komnaty będącej początkiem przejścia, a ki 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 kkj (1<=kkj<=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


Dodane przez:Michael Suchacz
Data dodania:2009-07-26
Limit czasu wykonania programu:0.100s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
Pochodzenie:Podlaski Turniej w Programowaniu Zespołowym
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.