Codeforces Round 151 (Div. 2) |
---|
Закончено |
Вам задан неориентированный граф, состоящий из n вершин и m ребер. Будем считать, что вершины графа пронумерованы целыми числами от 1 до n. Каждая вершина графа имеет цвет. Цветом i-ой вершины назовем целое число ci.
Рассмотрим все вершины графа, которые покрашены в некоторый цвет k. Обозначим множество таких вершин через V(k). Определим величину разноцветность соседей для цвета k как мощность множества Q(k) = {cu : cu ≠ k и существует вершина v принадлежащая множеству V(k) такая, что вершины 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-ое ребро.
Гарантируется, что в заданном графе нет петель и кратных ребер.
Выведите номер цвета, множество цветов соседей которого имеет максимальную мощность. Если оптимальных цветов несколько, выведите цвет с минимальным номером. Обратите внимание, что вы хотите найти такой цвет, что в графе существует хотя бы одна вершина с таким цветом.
6 6
1 1 2 3 5 8
1 2
3 2
1 4
4 3
4 5
4 6
3
5 6
4 2 5 2 4
1 2
2 3
3 1
5 3
5 4
3 4
2
Название |
---|