战略游戏
描述
省选临近,放飞自我的小 Q 无心刷题,于是怂恿小 C 和他一起颓废,玩起了一款战略游戏。
这款战略游戏的地图由 个城市以及 条连接这些城市的双向道路构成,并且从任意一个城市出发总能沿着道路走到任意其他城市。现在小 C 已经占领了其中至少两个城市,小 Q 可以摧毁一个小 C 没占领的城市,同时摧毁所有连接这个城市的道路。只要在摧毁这个城市之后能够找到某两个小 C 占领的城市 和 ,使得从 出发沿着道路无论如何都不能走到 ,那么小 Q 就能赢下这一局游戏。
小 Q 和小 C 一共进行了 局游戏,每一局游戏会给出小 C 占领的城市集合 ,你需要帮小 Q 数出有多少个城市在他摧毁之后能够让他赢下这一局游戏。
格式
输入格式
第一行包含一个正整数 ,表示测试数据的组数,
对于每组测试数据,
第一行是两个整数 和 ,表示地图的城市数和道路数,
接下来 行,每行包含两个整数 和 ,表示第 个城市和第 个城市之间有一条道路,同一对城市之间可能有多条道路连接,
第 是一个整数 ,表示游戏的局数,
接下来 行,每行先给出一个整数 ,表示小 C 占领的城市数量,然后给出 个整数 ,表示小 C 占领的城市。
输出格式
对于每一局游戏,输出一行,包含一个整数,表示这一局游戏中有多少个城市在小 Q 摧毁之后能够让他赢下这一局游戏。
样例1
样例输入1
样例输出1
限制
- ,
- 且 ,
- ,
- 对于每组测试数据,有。
子任务1(30分):对于每组测试数据,满足 。
子任务2(45分):对于每一次询问,满足 。
子任务3(25分):没有任何附加的限制。
来源
SDOI 2018 Round2