W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.