城市规划：求建设难度最小的城市编号

时间限制

1.0 s

内存限制

512.0 MB

题目描述

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

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

现在A国正在规划城市建设方案。城市 u 的建设难度为它到其它城市的最大连通度，即求使得 $\max_{1\leq i\leq n} d(u,i)$ 最小的 u，若存在多个满足条件的 u 则选取其中编号最小的。

输入格式

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

输出格式

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

样例

输入样例1

3 3
1 2
1 3
2 3

输出样例1

1

输入样例2

4 4
1 2
2 3
3 4
2 4

输出样例2

2

数据范围

• 对于 40% 的测试点，保证 1 ≤ n ≤ 300
• 对于所有测试点，保证 1 ≤ n ≤ 2000，1 ≤ m ≤ 2000，1 ≤ u_i, v_i ≤ n