城市规划

题目描述

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

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

现在 A 国正在规划城市建设方案。城市 i 的建设难度为它到其它城市的最大连通度。请你求出建设难度最小的城市，如果有多个满足条件的城市，则选取其中编号最小的城市。

输入格式

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

输出格式

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

样例

输入样例 1

3 3 1 2 1 3 2 3

输出样例 1

1

样例解释 1

三个城市两两相邻，每个城市到其它城市的最大连通度均为 1，取编号最小的城市 1。

输入样例 2

4 4 1 2 2 3 3 4 2 4

输出样例 2

2

数据范围

对于所有测试点，保证 1 <= n <= 2000，0 <= m <= n(n-1)/2，图连通。