Encontrar o Vértice Mais Pesado em um Grafo

Dado um grafo não dirigido com v vértices e e arestas, a sua tarefa é encontrar o vértice mais "pesado". O “peso” de um vértice é definido pelo número de conexões que ele possui. Quanto mais vizinhos um vértice tiver, maior será o seu “peso”. Se vários vértices tiverem o mesmo peso máximo, deve-se retornar aquele que tiver o menor número.

Entrada

A primeira linha da entrada contém dois inteiros v (1 ≤ v ≤ 1000) e e (1 ≤ e ≤ 100 000).

Nas e linhas seguintes, encontram-se pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v), indicando que o vértice v1 está conectado ao vértice v2 e vice-versa.

Saída

O programa deve imprimir o menor índice do vértice que tiver o maior peso.

Exemplos

Explicação