Barykady

Limit pamięci: 32 MB

Bajtocja to wyspa, na której znajduje się pewna liczba miast połączonych dwukierunkowymi drogami. Sieć dróg jest tak skonstruowana, że między każdą parą miast, bez zawracania, można przejechać na dokładnie jeden sposób.

Niestety nastały ciężkie czasy - Bajtocja przygotowuje się na wojnę. Główny strateg Bajtazar opracowuje plan obrony Bajtocji, który przewiduje utworzenie specjalnej strefy bezpieczeństwa. Powstanie ona przez zabarykadowanie niektórych z istniejących dróg w państwie tak, że staną się one kompletnie nieprzejezdne. Ażeby strefa była rzeczywiście bezpieczna, następujące warunki muszą być spełnione:

• z każdego miasta strefy musi się dać przejechać do każdego innego miasta strefy,
• z żadnego miasta poza strefą nie może się dać dojechać do jakiegokolwiek miasta w strefie,
• do strefy musi należeć dokładnie miast.

Rozważane są różne scenariusze - dla różnych wartości należy określić ile co najmniej dróg trzeba zabarykadować, by z takiej liczby miast stworzyć specjalną strefę bezpieczeństwa. Pomóż Bajtazarowi! Opracuj program, który obliczy konieczną liczbę barykad.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis sieci dróg w Bajtocji oraz zestaw zapytań z pewnymi wartościami ,
• dla każdego zapytania określi najmniejszą możliwą ilość barykad, które wystarczają do utworzenia strefy złożonej z miast (choćby na jeden sposób),
• wypisze wyniki na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę naturalną (), jest to liczba miast w Bajtocji. Miasta są ponumerowane liczbami .

Kolejne wierszy wejścia zawiera pary liczb naturalnych () oddzielone spacjami. Para oznacza, że w Bajtocji jest bezpośrednia droga między miastami o numerach i . Między dwoma miastami istnieje co najwyżej jedna droga.

W następnym wierszu wejścia zapisana jest liczba (), jest to liczba zapytań. W kolejnych wierszach zapisane są, po jednej w wierszu, liczby naturalne (). Określają one kolejne zapytania - liczby miast, z których należy utworzyć specjalną strefę bezpieczeństwa.

Wyjście

Twój program powinien wypisać dokładnie liczb, po jednej w wierszu. Liczbą w -tym wierszu powinna być:

• , jeśli utworzenie strefy z dokładnie miast nie jest możliwe,
• w przeciwnym razie minimalna liczba dróg, które trzeba zabarykadować, by utworzyć strefę złożoną z pewnych miast.

Przykład

7
1 2
1 3
2 4
2 5
3 6
3 7
2
2
3

2
1

Autor zadania: Marek Turski.