Dominant Set

题目描述

In graph theory, a dominant set for an undirected graph $G=(V,E)$ is a subset $D$ of $V$ such that every vertex not in $D$ is adjacent to at least one member of $D$. Finding the minimum dominant set is an NP-hard problem. Your job is to verify, for a given graph, if a subset of vertices is a dominant set.

输入格式

Each input file contains one test case. For each case, the first line contains $2$ positive integers: $n (≤10^4)$, the number of vertices; and $m (≤10^5)$, the number of edges. Then $m$ lines follow, each gives indices of the two ends of an edge. The vertices are indexed from $1$ to $n$. Then a positive integer $K (≤10^3)$ is given, followed by $K$ lines of vertex sets. Each set is given in the format:

k v[1] v[2] ... v[k]

where $k$ is the number of vertices in the set, and it is followed by $k$ distinct indices of vertices.

输出格式

For each given set, print in a line yes if it is a dominant set, or no if not.

样例 #1

样例输入 #1

8 9
1 2
2 3
3 4
4 5
5 6
5 7
6 7
6 1
3 6
4
4 1 3 5 8
5 8 7 6 4 2
5 1 2 3 4 5
8 8 7 6 5 4 3 2 1

样例输出 #1

yes
yes
no
yes