BZPRO

#3402. [Usaco2009 Open]Hide and Seek 捉迷藏

内存限制：128 MiB 时间限制：3 Sec
提交 提交记录 讨论

题目描述

    贝茜在和约翰玩一个“捉迷藏”的游戏．
    她正要找出所有适合她躲藏的安全牛棚．一共有N(2≤N≤20000)个牛棚，被编为1到N号．她知道约翰（捉牛者）从牛棚1出发．所有的牛棚由M(1≤M≤50000)条双向路连接，每条双向路连接两个不同的牛棚．所有的牛棚都是相通的．贝茜认为同牛棚1距离最远的的牛棚是安全的．两个牛棚间的距离是指，从一个牛棚到另一个牛棚最少需要通过的道路数量．请帮贝茜找出所有的安全牛棚．

输入格式

    第1行输入两个整数N和M，之后M行每行输入两个整数，表示一条路的两个端点．
   

输出格式

 仅一行，输出三个整数．第1个表示安全牛棚（如果有多个，输出编号最小的）；第2个表示牛棚1和安全牛棚的距离；第3个表示有多少个安全的牛棚．

样例

样例输入


			
6 7

3 6

4 3

3 2

1 3

1 2

2 4

5 2

样例输出


			
4 2 3

数据范围与提示

BZPRO Powered by Remmina.
Github Repository