/ OIer TK / 题库 /

战略游戏

战略游戏

测试数据来自 system/2045

描述

省选临近,放飞自我的小 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 \leq u < v \leq n)\),表示第 \(u\) 个城市和第 \(v\) 个城市之间有一条道路,同一对城市之间可能有多条道路连接,

第 \(m+1\) 是一个整数 \(q\),表示游戏的局数,

接下来 \(q\) 行,每行先给出一个整数 \(|S|~(2 \leq |S| \leq n)\),表示小 C 占领的城市数量,然后给出 \(|S|\) 个整数 \(s_1, s_2, \cdots, s_{|S|}\) \((1 \leq s_1 < s_2 < \cdots < s_{|S|} \leq n)\) ,表示小 C 占领的城市。

输出格式

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

样例1

样例输入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\le T\le 10\),
  • \(2\le n\le 10^5\) 且 \(n-1\le m\le 2\times 10^5\),
  • \(1\le q\le 10^5\),
  • 对于每组测试数据,有\(\sum |S| \leq 2\times 10^5\)。

子任务1(30分):对于每组测试数据,满足 \(\sum |S| \leq 20\)。

子任务2(45分):对于每一次询问,满足 \(|S| = 2\)。

子任务3(25分):没有任何附加的限制。

来源

SDOI 2018 Round2

信息

ID
1977
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者