← 返回题目列表

Codeforces · 613/D

D. 王国及其城市

中文机器翻译题面 查看原题

与此同时,K王国正在为国王的女儿的婚礼做准备。不过,为了不在亲戚面前丢面子,国王应该先完成国内的改革。由于国王等不及女儿出嫁,改革必须尽快完成。

王国目前由n个城市组成。城市之间由n-1条双向道路连接,这样人们就可以从任何一个城市到达任何另一个城市。由于国王必须节省很多钱,所以任何两个城市之间都只有一条路。

改革的重点是什么?国家的主要部委应该转移到不同的城市(我们称这些城市为重要城市)。然而,由于遭到野蛮人袭击的风险很高,因此必须小心谨慎。国王制定了几个计划,每个计划都由一组重要城市描述,现在想知道什么是最好的计划。

野蛮人可以占领一些不重要的城市(重要的城市肯定有足够的保护),之后被占领的城市就无法通行。特别是,该计划的一个有趣的特点是,野蛮人需要占领的最少城市数量才能使所有重要城市孤立,即从所有重要城市中无法到达任何其他重要城市。

帮助国王计算他的每个计划的这个特征。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 100 000) — 王国中的城市数量。

接下来的 n - 1 行中的每一行都包含两个不同的整数 ui, vi (1 ≤ ui, vi ≤ n) — 第 i 条道路连接的城市的索引。确保您只需沿现有道路即可从任何城市前往任何其他城市。

下一行包含一个整数 q (1 ≤ q ≤ 100 000) — King 计划的数量。

接下来的 q 行如下所示:首先是数字 ki — 国王计划中重要城市的数量 (1 ≤ ki ≤ n),然后紧接着 ki 个空格分隔的从 1 到 n 的成对不同数字 — 该计划中重要城市的数量。

所有 ki 的总和不超过 100 000。

输出

对于每个计划,打印一个整数 - 野蛮人需要占领的最小城市数量,或者如果所有野蛮人孤立重要城市的尝试都无效,则打印 - 1。

示例

输入 #1

4
1 3
2 3
4 3
4
2 1 2
3 2 3 4
3 1 2 4
4 1 2 3 4

输出 #1

1
-1
1
-1

输入 #2

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

输出 #2

2

注意

在第一个样本中,在第一个和第三个国王计划中,野蛮人可以占领城市 3,这就足够了。在第二个和第四个计划中,他们的所有尝试都不会有效。

在第二个样本中,要捕获的城市是 3 和 5。