Byteland is an island with a number of cities connected by two-way roads. Road network is designed in such a way, that there is exactly one possibility to drive between any pair of cities (without turning back).
Unfortunately, hard times have come - Byteland is preparing for a war. The Lead Strategiest of Byteland is preparing a plan of defence of Byteland, which takes into account creation of a special security zone. The zone will be created by blocking some of the existing roads in Byteland in such a way, that it won't be possible to drive through these roads. In order to make the zone completely secure, following rules have to be fulfilled:
cities.
, it is required to
determine how many roads have to be blocked at minimum, to obtain a special security zone of
size
(consisting of exactly
cities). Help the Lead Strategiest of Byteland - write a program which for specified value of
calculates required number of barricades.
Write a program which:
values),
The first line of the standard input contains one integer
(
),
representing the number of cities in Byteland.
Cities are numbered with numbers
.
Each of the following
lines of the standard input contains pair of integers
(
)
separated with single space. Pair
represents a direct road connecting cities
and
.
Each pair of cities is connected with at most one direct road.
In the following line of the standard input there is an integer
(
) - it is the number of queries to process.
Each of the following
lines contains one integer
(
). It represents query number
- the number of cities that have to be inside
'th special security zone.
Your program should write to the standard output exactly
numbers, each of them in a separate line.
The number in
'th line should be:
, if creation of a special security zone of size
is not possible,
otherwise.
For the input data:
7 1 2 1 3 2 4 2 5 3 6 3 7 2 2 3
the correct result is:
2 1
Task author: Marek Turski.
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.