Algorithms and Data Structures

Find the Heaviest Vertex in a Graph

Given an undirected graph with v vertices and e edges, you are asked to find its heaviest vertex. The “heaviness” of a vertex is measured by the number of connections. The more neighbors it has - the heavier the vertex. If several vertices have the same heaviest weight, you should return the one with the smallest number.

Input

The first line of the input contains two integers v (1 ≤ v ≤ 1000) and e (1 ≤ e ≤ 100 000).
The following e lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.

Output

The program should print the smallest index of the vertex with the heaviest weight.

Examples

Input
Output
8 9 1 4 4 6 3 2 2 1 5 2 5 6 8 5 7 6 7 8
2

Explanation

Vertices 2, 5, and 6 have 3 neighbors. Therefore the one with the smallest index is the vertex with number 2 ⇒ 2 is the correct answer.
Vertices 2, 5, and 6 have 3 neighbors. Therefore the one with the smallest index is the vertex with number 2 ⇒ 2 is the correct answer.

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue