Strategic City Destruction

In this problem, you are given an undirected connected graph consisting of n cities and m bidirectional roads. A strategic game is played on this map. In each round of the game, player C has occupied a set S of cities (with |S| ≥ 2). Player Q is allowed to choose a city that is not in S and destroy it – when a city is destroyed, all roads incident to it are also removed from the graph.

Player Q wins this round if, after removing the chosen city (and its incident roads), there exist two cities u and v in S such that there is no path between u and v in the remaining graph.

You are given q rounds. For each round, you are provided with the set S (the cities occupied by player C). Your task is to count the number of cities (which are not in S) such that, if that city is destroyed, player Q wins the game.

Note: The graph is guaranteed to be connected and may contain articulation points. Only the destruction of an appropriate articulation point (i.e. a vertex whose removal disconnects the graph into two or more connected components) can potentially disconnect the set S. However, even if a vertex is an articulation point, it is a winning move if and only if after its removal the cities in S are not all in the same connected component.

Formally: Let the graph be \(G=(V,E)\) and let S ⊆ V be the set of occupied cities with \(|S| \ge 2\). For a vertex \(v \in V \setminus S\), if in \(G - \{v\}\) there exist two cities \(u,v' \in S\) that lie in different connected components, then destroying \(v\) guarantees a win.

All formulas are written in LaTeX format.

inputFormat

The first line contains two integers n and m (\(1 \le n \le 10^5\), \(1 \le m \le 10^5\)), representing the number of cities and roads respectively.

The next m lines each contain two integers u and v (\(1 \le u,v \le n\)) denoting a bidirectional road between cities u and v. It is guaranteed that the graph is connected.

The following line contains an integer q (\(1 \le q \le 10^5\)), the number of rounds.

Each of the next q rounds is described as follows: The first number is an integer k (\(2 \le k \le n\)), denoting the number of cities occupied by player C. Then follow k distinct integers representing the indices of the occupied cities.

outputFormat

For each round, output a single integer on a new line: the number of cities that, if destroyed, guarantee a win for player Q.

sample

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

2
0
1