题目描述

国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。

我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。

在 $2$ 个国家 $a,b$ 之间建一条新通道需要的代价为树上 $a,b$ 的最短路径的长度。

现在国家有很多个计划，每个计划都是这样，我们选中了 $k$ 个点，然后在它们两两之间 新建 $\dbinom{k}{2}$ 条新通道。

现在对于每个计划，我们想知道：

1. 这些新通道的代价和。
2. 这些新通道中代价最小的是多少。
3. 这些新通道中代价最大的是多少。

输入格式

第一行 $n$ 表示点数。

接下来 $n-1$ 行，每行两个数 $a,b$ 表示 $a$ 和 $b$ 之间有一条边。点从 $1$ 开始标号。

接下来一行 $q$ 表示计划数。对每个计划有 $2$ 行，第一行 $k$ 表示这个计划选中了几个点。

第二行用空格隔开的 $k$ 个互不相同的数表示选了哪 $k$ 个点。

输出格式

输出 $q$ 行，每行三个数分别表示代价和，最小代价，最大代价。

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

提示

对于 $100\%$ 的数据，$1\le n\le 10^6,1\le q\le 5\times 10^4,\sum k\le 2\times n$。

每个测试点的具体限制见下表：