# 题目

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. Now given a graph with several vertex sets, you are supposed to tell if each of them is a vertex cover or not.

### Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N and M (both no more than 104), being the total numbers of vertices and the edges, respectively. Then M lines follow, each describes an edge by giving the indices (from 0 to N−1) of the two ends of the edge.

After the graph, a positive integer K (≤ 100) is given, which is the number of queries. Then K lines of queries follow, each in the format:

$N_v\; v[1]\; v[2] \cdots v[N_v]$

where $N_v$ is the number of vertices in the set, and v[i]'s are the indices of the vertices.

### Output Specification:

For each query, print in a line Yes if the set is a vertex cover, or No if not.

# 题解

## 思路

• 题目意思是给你一个图，然后给你一堆节点，让你判断和这些点相邻的所有道路是不是涵盖了整张图的道路
• 所以我们要考虑的首要问题是怎么表示一个道路
• 我们可以给定一个虚拟的道路编号，从0开始，一直到给定的道路数量-1
• 这样子，我们可以在读取的时候，读到两个节点，那么这两个节点的道路数组中都添加这一条道路编号，同时道路编号+1
• 在查询的时候，我们预设每条道路都是没有访问过的。
• 然后对查询的每个节点，标记它的所有道路为访问过
• 最后遍历所有的道路有没有被访问过即可。

## 数据结构

• 下标是节点的id
• 值是这个节点所联通的所有道路的编号的数组
• index 是边读取边更新的道路下标
• nodes 是所有查询中读取到的节点列表
• visited 标记哪些道路是已经走过的列表
• 下标是道路id
• 值是True或False

• 都写在思路里了。

## 代码

• 由于使用Python能AC，因此使用了Python的题解。