A 国有 n 座城市，城市之间由 m 条双向道路连接，任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以 1, 2, \ldots, 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 的双向道路。

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

数据范围

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

GESP25年12月七级

GESP七级25年12月图论最短路