题目描述

A国有n座城市，城市之间由m条双向道路连接，任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以1, 2, ..., n编号。第i(1 ≤ i ≤ m)条双向道路连接城市uᵢ与城市vᵢ。

对于城市u和城市v而言，它们之间的连通度d(u, v)定义为从城市u出发到达城市v所需经过的双向道路的最少条数。由于道路是双向的，可以知道连通度满足d(u, v) = d(v, u)，特殊地有d(u, u) = 0。

现在A国正在规划城市建设方案。城市u的建设难度为它到其它城市的最大连通度。请你求出建设难度最小的城市，如果有多个满足条件的城市，则选取其中编号最小的城市。形式化地，你需要求出使得max₁≤i≤n d(u, i)最小的u，若存在多个可能的u则选取其中最小的。

输入格式

第一行，两个正整数n, m，表示A国的城市数量与双向道路数量。 接下来m行，每行两个整数uᵢ, vᵢ，表示一条连接城市uᵢ与城市vᵢ的双向道路。

输出格式

输出一行，一个整数，表示建设难度最小的城市编号。如果有多个满足条件的城市，则选取其中编号最小的城市。

样例

输入样例 1

3 3
1 2
1 3
2 3

输出样例 1

1

输入样例 2

4 4
1 2
2 3
3 4
2 4

输出样例 2

2

数据范围

对于部分测试点，保证1 ≤ n ≤ 300。 对于所有测试点，保证1 ≤ n ≤ 2000，1 ≤ m ≤ 2000，1 ≤ uᵢ, vᵢ ≤ n。