P7011狡兔三窟 | ||
|
Description
nodgd发现了野生的兔子,但转眼间兔子就已经钻进地洞。
野外是一个树形结构, \(n\) 个节点编号分别为 $1,2,\cdots,n$ , \(n-1\) 条边第 \(i\) 条边连接节点 \(x_i,y_i\) ,每条边长度都是 $1$ 。
根据nodgd多年的研究,兔子的洞穴有且仅有一条主要通道,主要通道一定是树上的一条简单路径(长度可能为 $0$ )。兔子依靠洞口进出,为了方便,每个洞口到主要通道的距离总是不超过 $1$ 。
为了抓到野生兔子,nodgd找遍所有节点发现了 \(k\) 个洞口,分布在节点 \(p_1,p_2,\cdots,p_k\) 。nodgd想要通过这些信息推测兔子洞穴的主要通道可能在哪里,但问题在于节点太多了难以手动计算,所以请你写个程序帮忙计算。
Input Format
第一行两个整数 \(n,q\) ,表示节点数和询问的次数。
接下来 \(n-1\) 行,每行两个整数 \(x_i,y_i\) 表示一条边。
接下来 \(q\) 行每行一个询问。第一个整数 \(k\) 表示洞口的数量,接下来$k$ 个互不相同的整数 \(p_1,\cdots,p_k\) 。
Output Format
每次询问输出一行。
- 如果存在符合要求的主要通道,先输出
YES
然后再输出两个整数,表示主要通道的两个端点的节点编号,中间用空格间隔。如果有很多条符合要求的主要通道,你可以随便输出一种。 - 如果不存在符合要求的主要通道,输出
NO
。
Sample Input
10 5
1 2
2 3
1 4
4 5
1 6
6 7
7 8
6 9
7 10
10 1 2 3 4 5 6 7 8 9 10
3 3 5 7
3 3 4 10
3 2 4 6
4 2 4 9 10
Sample Output
NO
NO
YES 3 10
YES 1 1
YES 1 7
Hint
对于所有测试数据, $1\leq n,q,\sum k\leq 2\cdot10^5$ , $1\leq x_i,y_i,k,p_i\leq n$ 。
每个子任务不捆绑,分值均匀分布在每个测试点上。
子任务 | \(\qquad\) | 分值 | \(\qquad\) | \(n\leq\) | \(\qquad\) | \(q\leq\) | \(\qquad\) | \(\sum k\leq\) | \(\qquad\) | 其他限制 |
---|---|---|---|---|---|---|---|---|---|---|
$1$ | $10$ | $50$ | $10$ | $200$ | ||||||
$2$ | $15$ | $200$ | $200$ | $200$ | ||||||
$3$ | $10$ | $2\ 000$ | $2\ 000$ | $2\ 000$ | 每次询问 \(k\leq 3\) | |||||
$4$ | $15$ | $2\ 000$ | $2\ 000$ | $2\ 000$ | ||||||
$5$ | $4$ | $200\ 000$ | $200\ 000$ | $200\ 000$ | 每条树边 \(y_i=x_i+1\) | |||||
$6$ | $4$ | $200\ 000$ | $200\ 000$ | $200\ 000$ | 每次询问 \(k\leq 2\) | |||||
$7$ | $12$ | $200\ 000$ | $200\ 000$ | $200\ 000$ | 每次询问 \(k\leq 3\) | |||||
$8$ | $10$ | $200\ 000$ | $200\ 000$ | $200\ 000$ | 每次询问 \(k\leq 5\) | |||||
$9$ | $20$ | $200\ 000$ | $200\ 000$ | $200\ 000$ |
Source nodgd