4550：[GESP202512七级] 城市规划
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 题目背景
2025 年 12 月 GESP C++ 七级编程第 1 题
## 题目描述
A 国有 $n$ 座城市，城市之间由 $m$ 条双向道路连接，任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以 $1,2,\dots,n$ 编号。第 $i$（$1 \leq i \leq 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$ 的双向道路。
## 输出格式
输出一行，一个整数，表示建设难度最小的城市编号。如果有多个满足条件的城市，则选取其中编号最小的城市。
## 样例
```input1
3 3
1 2
1 3
2 3
```
```output1
1
```
```input2
4 4
1 2
2 3
3 4
2 4
```
```output2
2
```
## 数据范围
对于 $40\%$ 的测试点，保证 $1\le n\le 300$。
对于所有测试点，保证 $1\le n\le 2000$，$1\le m\le 2000$, $1 \leq u_i, v_i \leq n$。