P4606 [SDOI2018] 战略游戏

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

无

无

- $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| \le 2 \times 10^5$。 ### Subtasks - 子任务 1 (30 分)：对于每组测试数据，满足 $\sum|S| \le 20$； - 子任务 2 (45 分)：对于每一次询问，满足 $|S| = 2$； - 子任务 3 (25 分)：没有任何附加的限制。