← 返回题目列表

Codeforces · 690/C2

C2. 大脑网络(中)

中文机器翻译题面 查看原题

对僵尸思维过程的进一步研究产生了有趣的结果。从上一个问题中我们知道,僵尸的神经系统由 n 个大脑和 m 个将一些对大脑连接在一起的大脑连接器组成。据观察,僵尸的智力主要取决于其神经系统的拓扑结构。更准确地说,我们将两个大脑 u 和 v (1 ≤ u, v ≤ n) 之间的距离定义为在这两个大脑之间传输思想时使用的大脑连接器的最小数量。僵尸的大脑潜伏期被定义为其任意两个大脑之间的最大距离。研究人员推测,大脑潜伏期是决定僵尸有多聪明的关键参数。通过编写一个程序来计算神经系统的大脑延迟,帮助他们测试这个猜想。

在这个问题中,您可以假设输入中给出的任何神经系统都是有效的,即它满足简单版本中的条件(1)和(2)。

输入

输入的第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 100000),分别表示大脑的数量(方便地编号为 1 到 n)和神经系统中大脑连接器的数量。在接下来的 m 行中,描述了大脑连接器。每个连接器都以它连接的一对大脑 a b 的形式给出(1 ≤ a,b ≤ n 且 a ≠ b)。

输出

打印一个数字——大脑延迟。

示例

输入 #1

4 3
1 2
1 3
1 4

输出 #1

2

输入 #2

5 4
1 2
2 3
3 4
3 5

输出 #2

3