Barricades

Byteland is an island whose cities are connected by two-way roads. The road network is built so that between any pair of cities there is exactly one route (as long as you never turn back). In other words, the cities and roads form a tree.

Hard times have come, and Byteland is preparing for war. The chief strategist wants to set up a special security zone by placing barricades on some roads so that no one can drive across a barricaded road. For the zone to be secure it must satisfy all of the following:

• from every city inside the zone you can reach every other city inside the zone;
• no one can drive from a city outside the zone into a city inside the zone;
• the zone contains exactly $k$ cities.

For several values of $k$ the strategist wants to know the minimum number of roads that must be barricaded to build a special security zone of exactly $k$ cities.

Write a program that reads the road network and the list of queries, and for each query prints to standard output the minimum number of barricades needed to build a special security zone of the requested size.

The first line contains an integer $n$ ($1 \le n \le 3000$), the number of cities. Cities are numbered $1, 2, \ldots, n$.

Each of the next $n - 1$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$) separated by a single space, describing a road that directly connects cities $a$ and $b$. Every pair of cities is joined by at most one direct road.

The next line contains an integer $m$ ($1 \le m \le n$), the number of queries. Each of the following $m$ lines contains one integer $k_i$ ($1 \le k_i \le n$): query $i$ asks for a special security zone that contains exactly $k_i$ cities.

Print exactly $m$ lines. Line $i$ must contain:

• $-1$, if a special security zone of exactly $k_i$ cities cannot be built;
• otherwise, the minimum number of roads that must be barricaded to build such a zone.