Description

With the NOI Qualifier approaching, carefree Xiao Q has no desire to practice problems. He coaxes Xiao C to slack off with him and play a strategic game.

The map of this strategic game consists of $n$ cities and $m$ undirected roads connecting these cities. From any city, it is always possible to reach any other city by following the roads.

Xiao C has already occupied at least two cities. Xiao Q may destroy one city not occupied by Xiao C, and simultaneously destroy all roads incident to that city. If, after destroying this city, there exist two cities $u$ and $v$ occupied by Xiao C such that starting from $u$ it is impossible to reach $v$ along the roads, then Xiao Q wins that round.

Xiao Q and Xiao C play $q$ rounds in total. In each round, you are given the set $S$ of cities occupied by Xiao C. You need to help Xiao Q count how many cities, if destroyed, would allow him to win that round.

Input Format

The first line contains a single integer $T$, the number of test cases.

For each test case:

• The first line contains two integers $n$ and $m$, the number of cities and the number of roads.
• The next $m$ lines each contain two integers $u$ and $v$ ($1 \le u < v \le n$), indicating there is a road between city $u$ and city $v$. There may be multiple roads between the same pair of cities.
• The $(m + 1)$-th line contains an integer $q$, the number of game rounds.
• The next $q$ lines: each line first gives an integer $|S|$ ($2 \le |S| \le n$), the number of cities occupied by Xiao C, followed by $|S|$ integers $S_1, S_2, \ldots, S_{|S|}$ ($1 \le S_1 < S_2 < \cdots < S_{|S|} \le n$), denoting the cities occupied by Xiao C.

Output Format

For each round, output a single line containing one integer: the number of cities whose destruction would allow Xiao Q to win that round.

2
7 6
1 2
1 3
2 4
2 5
3 6
3 7
3
2 1 2
3 2 3 4
4 4 5 6 7
6 6
1 2
1 3
2 3
1 4
2 5
3 6
4
3 1 2 3
3 1 2 6
3 1 5 6
3 4 5 6

0
1
3
0
1
2
3

Hint

Constraints

• $1 \le T \le 10$.
• $2 \le n \le 10^5$ and $n - 1 \le m \le 2 \times 10^5$.
• $1 \le q \le 10^5$.
• For each test case, $\sum |S| \le 2 \times 10^5$.

Subtasks

• Subtask 1 (30 points): For each test case, $\sum |S| \le 20$.
• Subtask 2 (45 points): For each query, $|S| = 2$.
• Subtask 3 (25 points): No additional constraints.

Translated by ChatGPT 5