Вам задан неориентированный граф, состоящий из n вершин и m ребер. Будем считать, что вершины графа пронумерованы целыми числами от 1 до n. Каждая вершина графа имеет цвет. Цветом i-ой вершины назовем целое число ci.
Рассмотрим все вершины графа, которые покрашены в некоторый цвет k. Обозначим множество таких вершин через V(k). Определим величину разноцветность соседей для цвета k как мощность множества Q(k) = {cu : cu ≠ k и существует вершина v принадлежащая множеству V(k) такая, что вершины v и u соединены ребром графа}.
От Вас требуется найти такой цвет k, для которого мощность множества Q(k) максимальна. Другими словами, вы хотите найти такой цвет, у которого соседи наиболее разноцветны. Обратите внимание, что вы хотите найти такой цвет k, что в графе существует хотя бы одна вершина с таким цветом.
Выходные данные
Выведите номер цвета, множество цветов соседей которого имеет максимальную мощность. Если оптимальных цветов несколько, выведите цвет с минимальным номером. Обратите внимание, что вы хотите найти такой цвет, что в графе существует хотя бы одна вершина с таким цветом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 6
1 1 2 3 5 8
1 2
3 2
1 4
4 3
4 5
4 6
|
3
|
|
2
|
5 6
4 2 5 2 4
1 2
2 3
3 1
5 3
5 4
3 4
|
2
|