Tree in Tree

Time limit6sMemory limit512 MB

Summary

For each vertex subset, count the edges in its minimal connecting subtree using Euler tour order and LCA checks.

Level: Hard8 of 10
Topics: Tree, DFS, Sorting, Binary search
Solved: No attempts yet

Problem

A tree is given. A tree is an undirected and connected graph with $n$ vertices and $n - 1$ edges. The vertices are labeled $1, 2, \ldots, n$ .

There are $q$ queries. In each query we choose a subset of the tree's vertices $P = \{v_1, v_2, \ldots, v_k\}$ and ask how many edges lie in the minimum spanning tree of the set $P$ . In other words, how many edges belong to at least one path between some vertices of the set $P$ ? Find the answers to all queries.

Input

The first line contains a positive integer $n$ ( $2 \le n \le 1\,000\,000$ ), the number of the tree's vertices.

Each of the next $n - 1$ lines contains two distinct positive integers $a, b$ ( $1 \le a, b \le n$ ) which mean that vertices $a$ and $b$ are connected by an edge.

The next line contains a positive integer $q$ ( $1 \le q \le 60\,000$ ), the number of queries.

Each of the next $q$ lines contains first a positive integer $k$ ( $k \ge 2$ ), the size of the set, and then $k$ distinct positive integers between $1$ and $n$ which are the vertices of the set from the problem statement.

The sum of the sizes $k$ over all queries is at most $300\,000$ .

Output

For each query, print the required number of edges on a separate line.

Examples2

Example 1

Input

Expected output

Example 2

Input

10
1 2
2 4
5 2
6 3
3 1
6 7
9 7
8 6
8 10
5
2 4 5
3 4 5 6
4 2 4 7 10
4 4 5 9 10
9 1 2 3 5 6 7 8 9 10

Expected output