B. Query on a Tree
time limit per test
3 s
memory limit per test
1024 mebibytes
input
standard input
output
standard output

You are given a tree where vertices are labeled with integers $$$1, 2, \ldots, N$$$.

For a subset of vertices $$$S \subseteq \{1, 2, \ldots, N\}$$$, we say two vertices $$$(u, v)$$$ are connected under $$$S$$$ if there exists a path that only passes through the vertices in $$$S$$$. Note that this includes endpoints of the path, so $$$u, v \in S$$$ should hold.

For example, consider the following tree and the set $$$S = \{1, 2, 3, 4, 5, 6\}$$$.

In this case, $$$(1, 2)$$$, $$$(3, 5)$$$ and $$$(4, 6)$$$ are connected under $$$S$$$, while $$$(1, 6)$$$ and $$$(2, 7)$$$ are not connected under $$$S$$$.

Let $$$\mathit{strength}(S)$$$ be the number of pairs of vertices $$$(u, v)$$$ such that $$$u \neq v$$$ and $$$(u, v)$$$ are connected under $$$S$$$. You are given $$$Q$$$ queries, where each query contains a set $$$S$$$. For each query, you should compute the quantity $$$\mathit{strength}(S)$$$.

Input

The first line contains a single integer $$$N$$$, the number of vertices ($$$2 \le N \le 250\,000$$$).

Each of the next $$$N - 1$$$ lines contains two space-separated integers $$$a$$$ and $$$b$$$: the vertices connected by an edge ($$$1 \le a, b \le N$$$). Together, the edges form a tree.

The next line contains a single integer $$$Q$$$, the number of queries ($$$1 \le Q \le 100\,000$$$).

Each of the next $$$Q$$$ lines contains a query, denoted by space-separated integers. A query starts with an integer $$$K$$$, the size of the set ($$$1 \le K \le N$$$). It is followed by $$$K$$$ distinct integers from $$$1$$$ to $$$N$$$ in arbitrary order: the vertices of set $$$S$$$.

The sum of $$$K$$$ in each test case is at most $$$1\,000\,000$$$.

Output

For each of the $$$Q$$$ queries, print a single line with the integer $$$\mathit{strength}(S)$$$ as defined above.

Example
Input
7
1 2
1 3
1 5
2 7
4 6
4 7
6
1 1
2 1 2
4 1 2 3 4
5 1 2 4 6 7
6 1 2 3 4 5 6
7 1 2 3 4 5 6 7
Output
0
1
3
10
7
21