题目详情题解（0）讨论（0）提交记录（0）

A85765.「SDOI2018」战略游戏

NOI/NOI+/CTSC

通过率：0%

时间限制：10.00s

内存限制：512MB

题目描述

省选临近，放飞自我的小 Q 无心刷题，于是怂恿小 C 和他一起颓废，玩起了一款战略游戏。

这款战略游戏的地图由 nn 个城市以及 mm 条连接这些城市的双向道路构成，并且从任意一个城市出发总能沿着道路走到任意其他城市。现在小 C 已经占领了其中至少两个城市，小 Q 可以摧毁一个小 C 没占领的城市，同时摧毁所有连接这个城市的道路。只要在摧毁这个城市之后能够找到某两个小 C 占领的城市 uu 和 vv，使得从 uu 出发沿着道路无论如何都不能走到 vv，那么小 Q 就能赢下这一局游戏。

小 Q 和小 C 一共进行了 qq 局游戏，每一局游戏会给出小 C 占领的城市集合 SS，你需要帮小 Q 数出有多少个城市在他摧毁之后能够让他赢下这一局游戏。

输入格式

第一行包含一个正整数 TT，表示测试数据的组数，

对于每组测试数据，

第一行是两个整数 nn 和 mm ，表示地图的城市数和道路数，

接下来 mm 行，每行包含两个整数 uu 和 v (1≤u<v≤n)v~(1 \leq u < v \leq n)，表示第 uu 个城市和第 vv 个城市之间有一条道路，同一对城市之间可能有多条道路连接，

第 m+1m+1 是一个整数 qq，表示游戏的局数，

接下来 qq 行，每行先给出一个整数 ∣S∣ (2≤∣S∣≤n)|S|~(2 \leq |S| \leq n)，表示小 C 占领的城市数量，然后给出 ∣S∣|S| 个整数 s1,s2,…,s∣S∣ (1≤s1<s2<⋯<s∣S∣≤n)s_1,s_2,\dots,s_{|S|}~(1 \leq s_1 < s_2 < \dots < s_{|S|} \leq n)，表示小 C 占领的城市。

输出格式

对于每一局游戏，输出一行，包含一个整数，表示这一局游戏中有多少个城市在小 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

说明/提示

对于 30%30\% 的分数， ∑∣S∣≤20\sum |S| \leq 20 。
对于另外 45%45\% 的分数，对于每一次询问，满足 ∣S∣=2|S| = 2 。
对于 100%100\% 的分数， 1≤T≤10,2≤n≤105,n−1≤m≤2×105,1≤q≤1051\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 ，且对于每组测试数据，有 ∑∣S∣≤2×105\sum |S| \leq 2\times 10^5 。

首页