王城中枢

题目描述

王国中共有 $n$ 座城镇，编号为 $1$ 到 $n$。城镇之间由 $m$ 条双向道路连接，并且保证整张道路网是连通的。

对于一座城镇 $u$，如果从它出发到所有其它城镇的最短路中，最远的那一条长度是 $d_u$，那么王国就把 $d_u$ 记作这座城镇的“中枢难度”。

现在国王准备选一座城镇作为全国中枢。他希望中枢难度尽量小；如果有多座城镇都能达到最小中枢难度，那么选择编号最小的那一座。

请你输出这座城镇的编号。

输入格式

第一行包含两个整数 $n, m$。

接下来 $m$ 行，每行包含两个整数 $u, v$，表示城镇 $u$ 和城镇 $v$ 之间有一条双向道路。

输出格式

输出一个整数，表示应被选为中枢的城镇编号。

输入输出样例 #1

输入 #1

4 4
1 2
2 3
3 4
2 4

输出 #1

2

输入输出样例 #2

输入 #2

3 3
1 2
1 3
2 3

输出 #2

1

数据范围

对于 $40\%$ 的数据，$1 \le n \le 300$。

对于 $100\%$ 的数据，$1 \le n \le 2000$，$0 \le m \le 2000$，且保证图连通。

建议

二刷、三刷