与此同时,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。