OI题库

Bessie正在玩捉迷藏游戏。（捉迷藏是这样玩的：在制定了奖罚规则后，玩家分为“捉”和“藏”两种，“藏”者有多个，在他们都藏起来后，由单独的一个“捉”者去找他们，这个游戏玩起来真是其乐无穷！）

Bessie正在盘算她要藏到哪个牛棚里，一共有N(2 <= N <= 20,000)个牛棚，编号为1～N。她知道“捉”者FJ会从1号牛棚开始找。有M(1<= M <= 50,000)条无向通路连接着所有的牛棚，其中通路i的两个端点分别为A_i和B_i(1<= A_i <= N; 1 <= B_i <= N; A_i != B_i)，任意两个牛棚之间都可互达。

Bessie觉得藏到跟1号牛棚距离最远的牛棚里会比较安全，（这里两个牛棚之间的距离是指从一个牛棚到另一个牛棚的最短路径）,请帮Bessie算一下最佳躲藏位置。

输入格式：
第1行：两个空格隔开的整数N，M；
第2～M+1行：第i+1行有两个整数A_i,B_i，即第i条路的两个端点；

输出格式：
一行，三个空格隔开的整数，分别为：离1号牛棚最远的牛棚编号（如果最远的有多个，输出编号最小的那个）；最远的牛棚与1号牛棚的最短路径；拥有此最短路径的牛棚个数。

输入输出样例：
hideseek.in
6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2

输入样例说明：
输入数据如图所示：
1--2--5
| /|
|/ |
3--4
|
6

hideseek.out
4 2 3

输出样例解释：
4，5，6号牛棚距1号牛棚的最短路径均为2，选4号输出是因为它的编号最小。