In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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:
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.
Napisz program, który:
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.
Twój program powinien wypisać dokładnie liczb, po jednej w wierszu.
Liczbą w
-tym wierszu powinna być:
7 1 2 1 3 2 4 2 5 3 6 3 7 2 2 3poprawną odpowiedzią jest:
2 1
Autor zadania: Marek Turski.