Maximum Defended Island

Tom is facing a strategic challenge on a set of islands that are interconnected by bridges. Each island is numbered from 1 to n. A bridge connects two distinct islands, forming an undirected graph. Tom wishes to place a defense tower on an island such that the number of directly connected islands (i.e. islands sharing a bridge with it) is maximized. In other words, if we denote the degree of an island as \(d(i)\) (i.e., the number of bridges incident to island \(i\)), then Tom wants to choose an island \(k\) such that

[ d(k) = \max_{1 \le i \le n} d(i). ]

If there are multiple islands with the same maximum degree, any one of them is an acceptable answer. Your task is to compute and print the number of that island.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains two space-separated integers \(n\) and \(m\): the number of islands and the number of bridges respectively.
• The following \(m\) lines each contain two integers \(a\) and \(b\) indicating that there is a bridge between island \(a\) and island \(b\).

outputFormat

The output should be printed on standard output (stdout). It consists of a single integer which is the island where placing the defense tower defends the maximum number of islands. If multiple islands satisfy this condition, output any one of them.

5 4
1 2
1 3
1 4
1 5

1