CSES - Barricades
  • Time limit: 0.50 s
  • Memory limit: 64 MB

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:

  • from each city inside the zone it has to be possible to drive to any other city inside that zone,
  • it is not possible to get from a city outside of the zone to the city inside the zone,
  • zone has to consist of exactly k cities.

Many different solutions to the problem are being considered - for different values of k, it is required to determine how many roads have to be blocked at minimum, to obtain a special security zone of size k (consisting of exactly k cities). Help the Lead Strategiest of Byteland - write a program which for specified value of k calculates required number of barricades.

Task

Write a program which:

  • reads from the standard input description of the roads in Byteland and the set of queries (different values),
  • for each query program should determine the minimal possible number of barricades that are sufficient to construct a special security zone of required size,
  • writes result to the standard output.

Input

The first line of the standard input contains one integer n, representing the number of cities in Byteland. Cities are numbered with numbers 1, 2, \ldots, n.

Each of the following n-1 lines of the standard input contains pair of integers a, b separated with single space. Pair a, b represents a direct road connecting cities a and b. Each pair of cities is connected with at most one direct road.

In the following line of the standard input there is an integer m - it is the number of queries to process. Each of the following m lines contains one integer k_i. It represents query number i - the number of cities that have to be inside i'th special security zone.

Output

Your program should write to the standard output exactly m numbers, each of them in a separate line. The number in i'th line should be:

  • -1, if creation of a special security zone of size k_i is not possible,
  • the minimal number of roads that have to be blocked in order to construct a special security zone of size k_i otherwise.

Constraints

  • 1 \le n \le 3000
  • 1 \le m \le n
  • 1 \le k_i \le n

Example

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.