Friends

問題文

処理研には $N$ 人の部員が所属しており、$1,2,\dots,N$ と番号が付けられています。
処理研の中で、最も友達の数が多い人が誰なのか気になった処理犬くんは、聞き込み調査を行うことにしました。
聞き込み調査で得られた $M$ 個の情報が与えられるので、最も友達の多い部員の番号を出力してください。友達の数が最も多い部員が複数考えられる場合は、その中で最も番号が小さい部員の番号を出力してください。なお、聞き込み調査で得られなかった友人関係は存在しないと仮定します。

$M$ 個の情報のうち、 $i \, (1 \leq i \leq M)$ 個目の情報は以下の形式で与えられます。
a_i b_i : $a_i$ と $b_i$ は友達である。

聞き込み調査により得られた情報であるため、重複した情報を持つ可能性がある点に注意してください。 例えば、以下のように重複した情報が複数回与えられることがあります。
1 2
2 1
1 2

制約

• $1 \leq N \leq 1000$
• $0 \leq M \leq 1000$
• $1 \leq a_i,b_i \leq N \, (1 \leq i \leq M)$
• $a_i \neq b_i \, (1 \leq i \leq M)$

入力

N M
a_1 b_1
a_2 b_2
...
...
a_M b_M

• $1$ 行目に処理研の部員数 $N$ 、聞き込み調査で得られた情報の数 $M$ が与えられます。
• $2$ 行目以降に $M$ 行で、聞き込み調査で得られた情報を与えられます。

出力

最も友達の多い部員の番号を出力してください。友達の数が最も多い部員が複数考えられる場合は、その中で最も番号が小さい部員の番号を出力してください。

入力例 1

4 2
1 2
1 3

出力例 1

1

聞き込み調査で得られた情報から、以下のことが分かります。

• 部員 $1$ は 部員 $2,3$ と友達なので、友達の数は $2$ です。
• 部員 $2$ は 部員 $1$ と友達なので、友達の数は $1$ です。
• 部員 $3$ は 部員 $1$ と友達なので、友達の数は $1$ です。
• 部員 $4$ の友達の数は $0$ です。

よって、最も友達が多いのは部員 $1$ なので、$1$ を出力します。

入力例 2

2 2
1 2
2 1

出力例 2

1

部員 $1,2$ は共に友達の数は $1$ です。 よって、その中で最も番号が小さい $1$ を出力します。

入力例 3

3 8
1 2
1 3
2 3
2 1
3 1
3 2
1 2
1 3

出力例 3

1