Connectivity Queries on an Undirected Graph

You are given an undirected connected graph with n vertices and m edges. The graph may have multiple edges but does not contain self-loops. You have k independent queries. In each query, you are asked to remove a set of edges from the graph. After the removals, determine whether the remaining graph is still connected.

Note: The queries are independent, i.e. the removals in one query do not affect the graph for subsequent queries.

A graph is said to be connected if there exists a path between every pair of vertices.

The answer for each query should be Yes if the remaining graph is connected, and No otherwise.

Mathematical Formulation:

Given a graph \(G=(V,E)\) with \(|V|=n\) and \(|E|=m\), and for each query a set \(R \subseteq E\) of edges to be removed, check whether \(G'=(V,E\setminus R)\) is connected. Use standard connectivity definitions.

inputFormat

The input is given as follows:

 n m
 u1 v1
 u2 v2
 ...
 um vm
 k
 c1 r1_1 r1_2 ... r1_c1
 c2 r2_1 r2_2 ... r2_c2
 ...
 ck rk_1 rk_2 ... rk_ck

Where:

• n and m are the number of vertices and edges respectively.
• Each of the next m lines contains two integers u and v representing an undirected edge connecting vertices u and v. The edges are numbered from 1 to m in the order of input.
• k is the number of queries.
• For each query, the first integer c denotes the number of edges to remove, followed by c integers which are the indices of the edges to remove.

All queries are independent.

outputFormat

For each query, print a single line containing Yes if the graph remains connected after removing the specified edges, or No otherwise.

sample

4 4
1 2
2 3
3 4
4 1
3
0
1 2
2 2 3

Yes
Yes
No