【bzoj3402】[Usaco2009 Open]Hide and Seek 捉迷藏

2014年9月26日1,3650

Description

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

Input

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

Output

 仅一行,输出三个整数.第1个表示安全牛棚(如果有多个,输出编号最小的);第2个表示牛棚1和安全牛棚的距离;第3个表示有多少个安全的牛棚.

Sample Input

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

Sample Output

4 2 3

题解

裸最短路