捉迷藏(Hide and Seek S)

题目描述

奶牛贝西和农夫约翰（FJ）玩捉迷藏，现在有 $N$ 个谷仓，FJ开始在第一个谷仓，贝西为了不让FJ找到她，当然要藏在距离第一个谷仓最远的那个谷仓了。现在告诉你 $N$ 个谷仓，和 $M$ 个两两谷仓间的“无向边”。每两个仓谷间当然会有最短路径，现在要求距离第一个谷仓（FJ那里）最远的谷仓是哪个（所谓最远就是距离第一个谷仓最大的最短路径）？如有多个则输出编号最小的。以及求这最远距离是多少，和有几个这样的谷仓距离第一个谷仓那么远。

输入格式

第一行：两个整数 $N$，$M$；

第 $2-M+1$ 行：每行两个整数，表示端点 $A_i$ 和 $B_i$ 间有一条无向边。

输出格式

仅一行，三个整数，两两中间空格隔开。表示：距离第一个谷仓最远的谷仓编号（如有多个则输出编号最小的），以及最远的距离，和有几个谷仓距离第一个谷仓那么远。

样例输入 #1

6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2

样例输出 #1

4 2 3

数据范围

农场的布局如下：

这里谷仓4，5，6距离1号谷仓都是2，但是4编号最小所以输出4.因此最远距离是2且有3个谷仓，依次输出：2和3。

$2\le n\le 50000,1\le m\le 50000$

感谢 wjcwinmt 的贡献翻译

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1200。

测试点分布

出处：原题链接