Найти «самую тяжёлую» вершину в графе
Дан неориентированный граф с количеством вершин
v и рёбер e. Ваша задача – определить вершину, имеющую наибольшее число соседей (то есть «самую тяжёлую» вершину). Чем больше у вершины соседей, тем выше её «тяжесть». Если несколько вершин имеют одинаковую максимальную «тяжесть», нужно вывести ту, у которой номер меньше всех.Входные данные
В первой строке содержатся два целых числа
v (1 ≤ v ≤ 1000) и e (1 ≤ e ≤ 100 000).В следующих
e строках даны пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v) — это означает, что вершина v1 соединена с вершиной v2 и наоборот.Выходные данные
Программа должна вывести номер (индекс) вершины, обладающей максимальным числом соседей. Если таких вершин несколько, следует вывести вершину с наименьшим номером.
Примеры
Входные данные | Выходные данные |
8 9
1 4
4 6
3 2
2 1
5 2
5 6
8 5
7 6
7 8 | 2 |
Пояснение
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB