P2951 [USACO09OPEN] Hide and Seek S
题目描述
奶牛贝西和农夫约翰（FJ）玩捉迷藏，现在有 $N$ 个谷仓，FJ开始在第一个谷仓，贝西为了不让FJ找到她，当然要藏在距离第一个谷仓最远的那个谷仓了。现在告诉你 $N$ 个谷仓，和 $M$ 个两两谷仓间的“无向边”。每两个仓谷间当然会有最短路径，现在要求距离第一个谷仓（FJ那里）最远的谷仓是哪个（所谓最远就是距离第一个谷仓最大的最短路径）？如有多个则输出编号最小的。以及求这最远距离是多少，和有几个这样的谷仓距离第一个谷仓那么远。
输入格式
第一行：两个整数 $N$，$M$；
第 $2-M+1$ 行：每行两个整数，表示端点 $A_i$ 和 $B_i$ 间有一条无向边。
输出格式
仅一行，三个整数，两两中间空格隔开。表示：距离第一个谷仓最远的谷仓编号（如有多个则输出编号最小的），以及最远的距离，和有几个谷仓距离第一个谷仓那么远。
说明/提示
农场的布局如下：
这里谷仓4，5，6距离1号谷仓都是2，但是4编号最小所以输出4.因此最远距离是2且有3个谷仓，依次输出：2和3。
$2\le n\le 50000,1\le m\le 50000$
感谢 wjcwinmt 的贡献翻译