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.|

WILCZKI - Magda-Wilczki

Magda, którą znacie z zadania o ciasteczkach, ma poważny problem. Chce mieć zwierzątko domowe. Ale nie jakiegoś psa, kota, czy chomika, ale wilka, a najlepiej kilka. Niestety jej rodzice nie chcą mieć w domu groźnych zwierząt. Postanowiła, bez ich wiedzy i zgody, wybrać się do lasu i złapać sobie czworonożnych przyjaciół.

Przygotowała już mapę lasu, na której zaznaczyła wszystkie ścieżki, polany na których przebywają wilczki oraz ich kryjówkę. Zastanawia się teraz, czy cała ta wyprawa ma sens, tzn. czy uda jej się złapać minimum jednego wilczka. W chwili, gdy Magda pojawi się w lesie (na polanie oznaczonej numerem 1), wszystkie wilczki zaczną uciekać najkrótszą drogą do kryjówki, a Magda zacznie je łapać. Aby złapać wilczka, Magda i dany wilczek muszą znajdować się w pewnym momencie na tej samej polanie. Dzięki swoim niezwykłym zdolnościom, w danej chwili Magda może złapać nieskończenie wiele wilczków.
 
Jak się zapewne domyślasz, Twoim zadaniem jest sprawdzić, ile wilczków złapie Magda. Należy założyć, że każda ścieżka w lesie ma taką samą długość, oraz że Magda i wilczki poruszają się z taką samą predkością, Magda nie musi cały czas poruszać się i na polanie z kryjówką może przebywać, przechodzić, łapać (ale tylko jeśli nie są już w kryjówce bo wtedy już za późno).

Input

W pierwszej linii wejścia podana jest ilość polan oraz ilość ścieżek w lesie (P, S<=10^6).
W kolejnych S liniach - opisy ścieżek, tzn. informacja o tym, że dana ścieżka łączy polanę A z polaną B.
Następnie liczba wilczków w lesie - W<=10^6.
W kolejnej linii W liczb - numery polan, na których początkowo znajdują się kolejne wilczki. Na jednej polanie może być kilka wilczków.
W ostatniej linii jedna liczba - numer polany, na której znajduje się kryjówka wilczków.

Output

Jedna liczba - ilość wilczków złapanych przez Magdę, lub napis "Nie", gdy wyprawa nie ma sensu i lepiej żeby Magda została w domu i jadła ciasteczka.

Example 1:

Input:
8 8 
1 2
2 3
3 4

3 5
2 6
5 6
5 7
6 8
4
4 5 6 7
3
 
Output:
2

Example 2:

Input:
3 2
1 2
2 3
2
2 3
3
 
Output: 
Nie

 


Dodane przez:Marek Mystkowski
Data dodania:2012-08-26
Limit czasu wykonania programu:0.100s-1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.