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
Dla danych wejściowych:
7
1 2
1 3
2 4
2 5
3 6
3 7
2
2
3
poprawną odpowiedzią jest:
2
1
Autor zadania: Marek Turski.