← 返回题目列表

Codeforces · 246/D

D. 彩色图

中文机器翻译题面 查看原题

你有一个无向图,由 n 个顶点和 m 个边组成。我们将考虑用 1 到 n 的整数编号的图的顶点。图的每个顶点都有一种颜色。第 i 个顶点的颜色是整数 ci。

让我们考虑图的所有顶点,这些顶点都被涂上了某种颜色 k。让我们表示一组,例如 V(k)。我们将颜色 k 的相邻颜色多样性的值表示为集合 Q(k) = {cu : cu ≠ k 的基数,并且存在属于集合 V(k) 的顶点 v,使得节点 v 和 u 通过图的边连接}。

你的任务是找到这样的颜色 k,使得集合 Q(k) 的基数最大。换句话说,您想要找到具有最多样化邻居的颜色。请注意,您想要找到这样一种颜色 k,即该图至少有一个具有这种颜色的顶点。

输入

第一行包含两个空格分隔的整数 n, m (1 ≤ n, m ≤ 105) — 相应地,图的顶点结束边的数量。第二行包含整数序列 c1, c2, ..., cn (1 ≤ ci ≤ 105) — 图顶点的颜色。行上的数字用空格分隔。

接下来 m 行包含边的描述:第 i 行包含两个空格分隔的整数 ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — 由第 i 条边连接的顶点的数量。

保证给定的图没有自环或重边。

输出

打印具有最大基数的邻居集的颜色的编号。如果有多个最佳颜色,则打印数量最少的颜色。请注意,您想要找到这样一种颜色,即图形至少有一个具有这种颜色的顶点。

示例

输入 #1

6 6
1 1 2 3 5 8
1 2
3 2
1 4
4 3
4 5
4 6

输出 #1

3

输入 #2

5 6
4 2 5 2 4
1 2
2 3
3 1
5 3
5 4
3 4

输出 #2

2