[SDOI2018]战略游戏

题目描述

省选临近,放飞自我的小 $Q$ 无心刷题,于是怂恿小 $C$ 和他一起颓废,玩起了一款战略游戏。 这款战略游戏的地图由 $n$ 个城市以及 $m$ 条连接这些城市的双向道路构成,并且从任意一个城市出发总能沿着道路走到任意其他城市。 现在小 $C$ 已经占领了其中至少两个城市,小 $Q$ 可以摧毁一个小 $C$ 没占领的城市,同时摧毁所有连接这个城市的道路。只要在摧毁这个城市之后能够找到某两个小 $C$ 占领的城市 $u$ 和 $v$,使得从 $u$ 出发沿着道路无论如何都不能走到 $v$,那么小 $Q$ 就能赢下这一局游戏。 小 $Q$ 和小 $C$ 一共进行了 $q$ 局游戏,每一局游戏会给出小 $C$ 占领的城市集合 $S$,你需要帮小 $Q$ 数出有多少个城市在他摧毁之后能够让他赢下这一局游戏。

输入输出格式

输入格式


第一行包含一个正整数 T,表示测试数据的组数 对于每组测试数据 第一行是两个整数 $n$ 和 $m$ ,表示地图的城市数和道路数 接下来 $m$ 行,每行包含两个整数 $u$ 和 $v (1 ≤ u < v ≤ n)$,表示第 u 个城市和第 $v$ 个城市之间有一条道路,同一对城市之间可能有多条道路连接 第 $m + 1$ 是一个整数 q,表示游戏的局数, 接下来 $q$ 行,每行先给出一个整数 $|S| (2 ≤ |S| ≤ n)$,表示小 $C$ 占领的城市数量,然后给出 $|S|$ 个整数 $(1 ≤ s1 < s2$ $< ...

输出格式


对于每一局游戏,输出一行,包含一个整数,表示这一局游戏中有多少个城市在小 $Q$ 摧毁之后能够 让他赢下这一局游戏。

输入输出样例

输入样例 #1

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

输出样例 #1

0
1
3
0
1
2
3

说明

- $1 ≤ T ≤ 10$ - $2 ≤ n ≤ 10^5$ 且$n-1≤m≤2×10^5$ - $1 ≤ q ≤ 10^5$ - 对于每组测试数据,有 $∑|S| ≤ 2 × 10^5$ ## Subtasks - 子任务 1 (30 分):对于每组测试数据,满足 $∑|S| ≤ 20$ - 子任务 2 (45 分):对于每一次询问,满足 $|S| = 2$ - 子任务 3 (25 分):没有任何附加的限制。