CF246D Colorful Graph

你得到一个无向图，该图包含 $n$ 个顶点和 $m$ 条边。我们将图中的顶点编号为 $1$ 到 $n$ 的整数。每个顶点都有一种颜色。第 $i$ 个顶点的颜色是一个整数 $c_i$。 我们考虑所有被涂成某种颜色 $k$ 的顶点，记这些顶点的集合为 $V(k)$。我们将颜色 $k$ 的邻接颜色多样性定义为集合 $Q(k)$ 的基数（即不同元素的个数），其中 $Q(k) = \{c_u : c_u \neq k \text{ 且存在顶点 } v \in V(k) \text{ 使得顶点 } v \text{ 和 } u \text{ 通过一条图的边相连}\}$。 你的任务是找到一种颜色 $k$，使得集合 $Q(k)$ 的基数最大。换句话说，你需要找到拥有最多不同相邻颜色的颜色。请注意，所找的颜色 $k$ 应当在图中至少出现过一次。

第一行包含两个用空格分隔的整数 $n,m$（$1 \leq n, m \leq 10^{5}$），分别表示图中的顶点数和边数。第二行包含一组整数 $c_1, c_2, ..., c_n$（$1 \leq c_i \leq 10^{5}$），依次表示每个顶点的颜色，数字之间用空格分隔。 接下来的 $m$ 行描述图的边：第 $i$ 行包含两个用空格分隔的整数 $a_i, b_i$（$1 \leq a_i, b_i \leq n; a_i \neq b_i$），表示第 $i$ 条边连接了顶点 $a_i$ 和 $b_i$。 保证给定的图中没有自环或重边。

输出拥有最大邻接色集合基数的颜色编号。如果有多个最优解，输出颜色编号最小的那个。请注意，所选的颜色在图中应至少出现过一次。

由 ChatGPT 5 翻译