BZPRO

#5329. [Sdoi2018]战略游戏

内存限制：512 MiB 时间限制：30 Sec
提交 提交记录 讨论

题目描述

省选临近，放飞自我的小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|个整数s1,s2,...s|S|,(1<=s1<s2<s|S|<=n)，表示小C占领的城市。
1<= T<= 10，
2<= n<= 10^5 且 n-1<= m<= 2*10^5，
1<= q<= 10^5，
对于每组测试数据，有Sigma|S|<= 2*10^5

输出格式

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

样例

样例输入


			
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

数据范围与提示

BZPRO Powered by Remmina.
Github Repository