Codeforces Round 339 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

divide and conquer

dp

graphs

sortings

trees

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Kingdom and its Cities

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMeanwhile, the kingdom of K is getting ready for the marriage of the King's daughter. However, in order not to lose face in front of the relatives, the King should first finish reforms in his kingdom. As the King can not wait for his daughter's marriage, reforms must be finished as soon as possible.

The kingdom currently consists of *n* cities. Cities are connected by *n* - 1 bidirectional road, such that one can get from any city to any other city. As the King had to save a lot, there is only one path between any two cities.

What is the point of the reform? The key ministries of the state should be relocated to distinct cities (we call such cities important). However, due to the fact that there is a high risk of an attack by barbarians it must be done carefully. The King has made several plans, each of which is described by a set of important cities, and now wonders what is the best plan.

Barbarians can capture some of the cities that are not important (the important ones will have enough protection for sure), after that the captured city becomes impassable. In particular, an interesting feature of the plan is the minimum number of cities that the barbarians need to capture in order to make all the important cities isolated, that is, from all important cities it would be impossible to reach any other important city.

Help the King to calculate this characteristic for each of his plan.

Input

The first line of the input contains integer *n* (1 ≤ *n* ≤ 100 000) — the number of cities in the kingdom.

Each of the next *n* - 1 lines contains two distinct integers *u*_{i}, *v*_{i} (1 ≤ *u*_{i}, *v*_{i} ≤ *n*) — the indices of the cities connected by the *i*-th road. It is guaranteed that you can get from any city to any other one moving only along the existing roads.

The next line contains a single integer *q* (1 ≤ *q* ≤ 100 000) — the number of King's plans.

Each of the next *q* lines looks as follows: first goes number *k*_{i} — the number of important cities in the King's plan, (1 ≤ *k*_{i} ≤ *n*), then follow exactly *k*_{i} space-separated pairwise distinct numbers from 1 to *n* — the numbers of important cities in this plan.

The sum of all *k*_{i}'s does't exceed 100 000.

Output

For each plan print a single integer — the minimum number of cities that the barbarians need to capture, or print - 1 if all the barbarians' attempts to isolate important cities will not be effective.

Examples

Input

4

1 3

2 3

4 3

4

2 1 2

3 2 3 4

3 1 2 4

4 1 2 3 4

Output

1

-1

1

-1

Input

7

1 2

2 3

3 4

1 5

5 6

5 7

1

4 2 4 6 7

Output

2

Note

In the first sample, in the first and the third King's plan barbarians can capture the city 3, and that will be enough. In the second and the fourth plans all their attempts will not be effective.

In the second sample the cities to capture are 3 and 5.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/18/2024 14:22:15 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|