给你一个有根树,由 $$$n$$$ 顶点组成,编号从 $$$1$$$ 到 $$$n$$$。树的根是顶点号$$$1$$$。
树是具有 $$$n-1$$$ 边的连通无向图。
您收到了 $$$m$$$ 查询。第 $$$i$$$ 查询由一组 $$$k_i$$$ 不同顶点 $$$v_i[1]、v_i[2]、\dots、v_i[k_i]$$$ 组成。你的任务是判断是否存在从根到某个顶点 $$$u$$$ 的路径,使得每个给定的 $$$k$$$ 顶点要么属于该路径,要么到该路径的某个顶点的距离为 $$$1$$$。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — 树中的顶点数和查询数。
接下来的 $$$n-1$$$ 行描述了树的一条边。边 $$$i$$$ 由两个整数 $$$u_i$$$ 和 $$$v_i$$$ 表示,它连接的顶点的标签 $$$(1 \le u_i, v_i \le n, u_i \ne v_i$$$)。
保证给定的边形成一棵树。
接下来的 $$$m$$$ 行描述查询。第 $$$i$$$ 行描述第 $$$i$$$ 查询,并以整数 $$$k_i$$$ ($$$1 \le k_i \le n$$$) 开头 — 当前查询中的顶点数。然后 $$$k_i$$$ 整数如下:$$$v_i[1], v_i[2], \dots, v_i[k_i]$$$ ($$$1 \le v_i[j] \le n$$$),其中 $$$v_i[j]$$$ 是第 $$$i$$$ 个查询的第 $$$j$$$ 个顶点。
保证单个查询中的所有顶点都是不同的。
保证 $$$k_i$$$ 之和不超过 $$$2 \cdot 10^5$$$ ($$$\sum\limits_{i=1}^{m} k_i \le 2 \cdot 10^5$$$)。
输出
对于每个查询,打印答案 —“是”,如果存在从根到某个顶点 $$$u$$$ 的路径,使得每个给定的 $$$k$$$ 顶点要么属于该路径,要么到该路径的某个顶点的距离为 $$$1$$$,否则为“否”。
示例
输入 #1
10 6 1 2 1 3 1 4 2 5 2 6 3 7 7 8 7 9 9 10 4 3 8 9 10 3 2 4 6 3 2 1 5 3 4 8 2 2 6 10 3 5 4 7
输出 #1
YES YES YES YES NO NO
注意
示例对应的图片:
考虑查询。
第一个查询是 $$$[3, 8, 9, 10]$$$。答案是“是”,因为您可以选择从根 $$$1$$$ 到顶点 $$$u=10$$$ 的路径。那么顶点 $$$[3, 9, 10]$$$ 属于从 $$$1$$$ 到 $$$10$$$ 的路径,顶点 $$$8$$$ 到也属于该路径的顶点 $$$7$$$ 的距离为 $$$1$$$。
第二个查询是 $$$[2, 4, 6]$$$。答案是“是”,因为您可以选择到达顶点 $$$u=2$$$ 的路径。那么顶点 $$$4$$$ 到属于该路径的顶点 $$$1$$$ 的距离为 $$$1$$$,而顶点 $$$6$$$ 到属于该路径的顶点 $$$2$$$ 的距离为 $$$1$$$。
第三个查询是 $$$[2, 1, 5]$$$。答案是“是”,因为您可以选择到顶点 $$$u=5$$$ 的路径,并且查询的所有顶点都属于该路径。
第四个查询是 $$$[4, 8, 2]$$$。答案是“是”,因为您可以选择到顶点 $$$u=9$$$ 的路径,因此顶点 $$$2$$$ 和 $$$4$$$ 到属于该路径的顶点 $$$1$$$ 的距离均为 $$$1$$$,而顶点 $$$8$$$ 到属于该路径的顶点 $$$7$$$ 的距离为 $$$1$$$。
第五个和第六个查询的答案都是“否”,因为您无法选择合适的顶点$$$u$$$。