CF1578K Kingdom of Islands

“群岛王国”由 $p$ 个岛屿组成。作为国王，你统治着整个王国，而每个岛屿由一个或多个“jarl”在你的统治下管理。你总共拥有 $n$ 个“jarl”。 王国的每个岛屿都有自己强烈的传统，因此管理同一岛屿的“jarl”们会互相支持，绝不会发生冲突。然而，这种团结也带来了不同岛屿居民之间的文化冲突。因此，管理不同岛屿的两个“jarl”之间会存在冲突。 不过，近年来“jarl”之间的传统关系发生了一些变化。据你所知，恰好有 $k$ 对“jarl”之间的关系与传统不同。具体来说，如果这对“jarl”管理同一个岛屿，他们之间会发生冲突；如果他们管理不同的岛屿，他们能够克服文化分歧，不再发生冲突。 作为一位负责任的国王，你担心王国是否接近一场重大冲突。为了评估当前的局势，你希望找到一个最大的“jarl”群体，使得群体中的任意两位“jarl”之间都存在冲突。

输入的第一行包含两个整数 $p$ 和 $n$（$1 \le p \le n \le 10^5$；$1 \le p \le 10^4$）。 第二行包含 $n$ 个整数 $s_1, s_2, \ldots, s_n$（$1 \le s_i \le p$）。其中 $s_i$ 表示第 $i$ 位“jarl”管理的是编号为 $s_i$ 的岛屿。保证每个岛屿至少有一位“jarl”管理。 第三行包含一个整数 $k$（$0 \le k \le 20$）。 接下来的 $k$ 行，每行包含两个不同的整数 $a_j$ 和 $b_j$（$1 \le a_j < b_j \le n$），表示第 $a_j$ 位和第 $b_j$ 位“jarl”之间的关系与传统不同。保证没有重复的“jarl”对。

第一行输出一个整数 $q$，表示可以选出的两两冲突的“jarl”最大数量（$1 \le q \le n$）。 第二行输出 $q$ 个不同的整数，表示选出的“jarl”的编号，顺序不限。

下图展示了最后一个样例测试点的冲突关系图。每个圆圈代表一个岛屿。  由 ChatGPT 4.1 翻译