CF553D Nudist Beach

“Nudist Beach” 正在策划一次针对“Life Fibers”的军事行动。在本次行动中，他们计划攻击并占领若干由“Life Fibers”控制的城市。 现在有 $n$ 个城市，编号为 $1$ 到 $n$，城市之间有 $m$ 条双向道路。当前，每个城市中都有“Life Fibers”的存在。此外，“Life Fibers”还有 $k$ 个城市作为堡垒，这些城市在任何情况下都无法被攻占。因此，“Nudist Beach”只能占领任意非空、且不包含堡垒城市的城市子集。 行动结束后，“Nudist Beach”还需要防御反击。如果他们占领了一个城市，而它与许多仍由“Life Fibers”控制的城市相连，该城市很容易被击败。因此，“Nudist Beach”希望选择一些城市，使得每一个被占领的城市，其被“Nudist Beach”控制的相邻城市在所有相邻城市中的比例尽可能高。 形式化地说，Nudist Beach 需要选择一个不包含任何堡垒的、非空城市集合 $S$。一个城市 $x$ 的“强度”定义为：$(x \text{ 在 } S \text{ 中的相邻城市数}) / (\text{城市 } x \text{ 的总相邻城市数})$。两个城市若通过一条道路相连，则被视为相邻城市。目标是最大化 $S$ 内最弱城市（即最小“强度”）的该指标。 给定该无向图以及所有堡垒城市，求出一个符合要求的非空子集 $S$，使得集合内最弱城市的“强度”达到最大，并输出 $S$ 的任意一种方案。

输入的第一行包含三个整数 $n, m, k$（$2 \leq n \leq 100000$，$1 \leq m \leq 100000$，$1 \leq k \leq n-1$）。 第二行包含 $k$ 个整数，表示有堡垒的城市编号，这些城市互不相同。 接下来的 $m$ 行，每行包含两个整数 $a_{i},b_{i}$（$1 \leq a_{i}, b_{i} \leq n$，$a_{i} \ne b_{i}$），表示第 $i$ 条道路连接 $a_i$ 和 $b_i$。每个城市至少有一条相连的道路。 任意一对城市之间最多只会有一条道路。

第一行输出一个整数 $r$，表示答案集合的大小（$1 \leq r \leq n-k$）。 第二行输出 $r$ 个整数，表示被占领的城市编号。这些城市可以按任意顺序给出，且不得包含任何堡垒城市。 如果有多组合法解，输出任意一组即可。

第一个样例的最大“强度”为 $1/2$，没有其他子集能取得更高值。 第二个样例的最大“强度”为 $1$，注意子集不要求连通。 由 ChatGPT 5 翻译