#HDR002B. 病毒

病毒

题目描述

题目描述最下方提供了简要题意。

你所在的城市有 nn 个居民,每个居民都有一个 1n1 \sim n 之间的互不相同的编号,每个居民每天都会与他的所有朋友依次见面(即不会同时与多个朋友见面)。为了简化题目,我们令这 nn 个居民之间的朋友关系组成一个树形结构。

nn 个居民中存在一个敌国间谍,其拥有一种特别的病毒,该病毒可以帮助敌国监视居民行动,所有感染该病毒的居民不会产生任何症状,也不会死亡,这使得普通居民无法判断其他居民和自己是否感染该病毒。第一天间谍会让自己感染该病毒,第二天间谍在白天与朋友见面时将病毒传染给他的朋友们,第三天间谍的朋友们会将病毒传染给他们各自的朋友,以此类推。但是由于该病毒对人体没有攻击力,在居民感染后的第二天体内就会产生抗体杀死病毒,并且在之后再与感染者见面时也不会再感染病毒。

不过警方早已知道间谍的阴谋,在某一天警方对全城的 nn 个居民进行了检查,发现其中有 kk 个居民感染上了该病毒。由于你是全城公认的小天才,警方将会告诉你这 kk 个感染者的编号,请你帮警方得出敌国间谍的编号和总感染时间(即从间谍自己感染病毒到警察找出 kk 个感染者的天数)。如果有多个居民可能为敌国间谍,警方会认为能使总感染时间最短的居民为间谍。如果找不到间谍请输出 -1

敌国非常狡猾,一共对你所在的城市派了 qq 次间谍,因此你需要帮警察解决 qq 次这样的问题。

简要题意:给出一个 nn 个点的树,然后有 qq 次询问,每次询问给出一个点集,询问树上是否存在一个点使得该点到点集中的所有点的距离相同。如果存在这样的点,输出这个点的编号和这个点到点集中任意一点的距离。如果不存在这样的点,输出 -1。如果存在多个满足条件的点,输出离点集中任意一点距离最近的满足条件的点的信息。

输入格式

第一行一个正整数 nn,表示城市中的居民数量。

接下来 n1n-1 行,一行两个整数 x,yx,y,表示编号为 xx 的居民和编号为 yy 的居民为朋友。

接着是一行一个正整数 qq,表示询问次数。

接着是 qq 行,每行第一个正整数为 kk,表示城市中感染者的数量,紧接着 kk 个正整数 a1, a2, a3, , aka_1,~a_2,~a_3,~\dots,~a_k,表示所有感染者的编号。

输出格式

输出共 kk 行,表示每个询问的答案,格式参考题目描述。

8
1 2
2 3
2 4
1 5
5 6 
5 7
7 8
5
1 1
2 3 4
3 1 6 7
2 2 6
4 3 4 6 7
1 0
2 1
5 1
-1
1 2

数据范围与提示

「本题采用捆绑测试」

Subtask 1(30 pts): 2n3000,k5000\texttt{Subtask 1(30 pts): }2 \le n \le 3000,\sum k \le 5000
Subtask 2(10 pts): \texttt{Subtask 2(10 pts): }对于每组询问,恒有 k=2k=2
Subtask 3(10 pts): \texttt{Subtask 3(10 pts): }保证 x[1,n1]\forall x\in[1,n-1], xxx+1x+1 有边。
Subtask 4(10 pts): \texttt{Subtask 4(10 pts): }保证 x[2,n]\forall x \in [2,n],xx11 有边。
Subtask 5(40 pts): \texttt{Subtask 5(40 pts): }无特殊限制。

对于 100%100\% 的数据,1<n106,1q5×105,k1061 < n \le 10^6,1 \le q \le 5 \times 10^5 ,\sum k \le 10^6

注意本题输入数据较大,你可能需要使用较快的读入方式。