Description

The country is undertaking a major project to build some new channels in a very large transportation network.

Our country has a very special layout. It can be regarded as a tree with unit edge weights, with cities at the vertices.

The cost of building a new channel between two cities $a,b$ is the length of the shortest path between $a,b$ on the tree.

There are many plans. In each plan, we select $k$ vertices, and then build $\dbinom{k}{2}$ new channels between every pair of them (exactly one between any two vertices).

For each plan, we want to know:

1. The sum of the costs of these new channels.
2. The minimum cost among these new channels.
3. The maximum cost among these new channels.

Input Format

The first line contains $n$, the number of vertices.

The next $n-1$ lines each contain two integers $a,b$, indicating there is an edge between $a$ and $b$. Vertices are numbered starting from $1$.

The next line contains $q$, the number of plans. For each plan, there are $2$ lines. The first line contains $k$, the number of selected vertices in this plan.

The second line contains $k$ distinct integers separated by spaces, indicating which $k$ vertices are selected.

Output Format

Output $q$ lines. Each line contains three numbers: the sum of costs, the minimum cost, and the maximum cost.

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

3 3 3 
6 6 6 
1 1 1 
2 2 2 
2 2 2

Hint

For $100\%$ of the testdata, $1 \le n \le 10^6, 1 \le q \le 5 \times 10^4, \sum k \le 2 \times n$.

The specific limits for each test point are shown in the table below:

Translated by ChatGPT 5