题目描述

给定一棵 $n$ 个点的树，定义 $f(S, x)$ 为 $S$ 中的点与 $x$ 的距离的最大值。形式化地，$f(S, x) = \max_{s \in S} \operatorname{dist}(x, s)$，其中 $\operatorname{dist}(x, y)$ 定义为 $x,y$ 之间的唯一的简单路径上的边数。

你需要回答 $q$ 次查询，每次查询给定一个点集 $S$，你需要回答 $\min_{1 \le i \le n} f(S, i)$。换言之，你需要选择一个点 $i$，使得 $S$ 中的点与 $i$ 的距离的最大值最小，且你只需要输出这个最小值。

输入格式

第一行一个正整数 $T$，代表数据组数。接下来 $T$ 组数据，每组数据的格式如下：

• 第一行两个正整数 $n,q$，代表树的点数和查询组数；
• 接下来 $n-1$ 行，第 $i$ 行两个整数 $x_i,y_i$，代表树中有一条 $x_i,y_i$ 之间的边；
• 接下来 $q$ 组查询，每组查询占两行。每组查询的格式如下：
  • 第一行一个整数 $|S|$，代表查询的点集 $S$ 的大小；
  • 接下来一行 $|S|$ 个整数，代表点集 $S$。

输出格式

对于每组数据，输出 $q$ 行，每行一个整数，代表该组查询的答案。

1
7 2
1 2
1 3
2 4
2 5
2 6
3 7
1
4
4
4 5 6 7

0
2

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 200$，$1 \le n,q \le 200$；
• 对于另外 $30\%$ 的数据，$|S| \le 10$；
• 对于 $100\%$ 的数据：
  • $1 \le T \le 10^5$；
  • $1 \le n,q \le 2 \cdot 10^5$，$1 \le \sum n, \sum q \le 2 \cdot 10^5$；
  • $1 \le |S| \le n$，$1 \le \sum |S| \le 2 \cdot 10^5$，保证输入的 $S$ 中的元素互不相同；
  • $1 \le x_i, y_i \le n$，保证输入的图是一棵树。