F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5329. -- [Sdoi2018]战略游戏

5329: [Sdoi2018]战略游戏

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 219  Solved: 137
[Submit][Status][Discuss]

Description

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

Input

第一行包含一个正整数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

Output

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

Sample Input

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

Sample Output

0
1
3
0
1
2
3

HINT

Source

[Submit][Status][Discuss]

HOME Back