P4606 [SDOI2018] Strategic Game

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.

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.

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

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