[USACO Open09]捉迷藏

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 hideseek.in 输出文件 hideseek.out

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号输出是因为它的编号最小。