城市规划

题目描述

A 国有 座城市，城市之间由 条双向道路连接，任意⼀座城市均可经过若⼲条双向道路到达另⼀座城市。城市依 次以 编号。第 （ ）条双向道路连接城市 与城市 。 对于城市 和城市 ⽽⾔，它们之间的连通度 定义为从城市 出发到达城市 所需经过的双向道路的最少条 数。由于道路是双向的，可以知道连通度满⾜ ，特殊地有 。 现在 A 国正在规划城市建设⽅案。城市 的建设难度为它到其它城市的最⼤连通度。请你求出建设难度最⼩的城 市，如果有多个满⾜条件的城市，则选取其中编号最⼩的城市。形式化地，你需要求出使得 最⼩的 ，若存在多个可能的 则选取其中最⼩的。

输入格式

第⼀⾏，两个正整数 ，表⽰ A 国的城市数量与双向道路数量。 接下来 ⾏，每⾏两个整数 ，表⽰⼀条连接城市 与城市 的双向道路。

输出格式

输出⼀⾏，⼀个整数，表⽰建设难度最⼩的城市编号。如果有多个满⾜条件的城市，则选取其中编号最⼩的城市。

样例输入 #1

3 3
1 2
1 3
2 3

样例输出 #1

1

样例输入 #2

4 4
1 2
2 3
3 4
2 4

样例输出 #2

2

数据范围

对于 的测试点，保证 。 对于所有测试点，保证 ， ， 。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。