P30108

vertax cover

难度 5 级 图的表示与存储 哈希 图论
讨论 统计 1通过 1提交 100%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

图的顶点覆盖是指一组顶点,使得图中的每条边都至少与这组顶点中的一个顶点相关联。现在给定一个图以及若干顶点集合,请你判断每个集合是否是一个顶点覆盖。

输入

每个输入文件包含一个测试用例。第一行给出两个正整数 N 和 M(均不超过 10^4),分别表示顶点总数和边数。

接下来 M 行,每行描述一条边,给出边的两个端点的编号(从 0 到 N-1)。

在图的描述之后,给出一个正整数 K(\le 100),表示查询的数量。

接下来 K 行查询,每行格式为: Nv v[1] v[2] ... v[Nv]

其中 Nv 是集合中顶点的数量,v[i] 是顶点的编号。

输出

对于每个查询,如果该集合是一个顶点覆盖,则输出 Yes,否则输出 No。

样例

样例 1
输入
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
5
4 0 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2
输出
No
Yes
Yes
No
No
Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交