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

[Usaco2009 Open]Hide and Seek 捉迷藏

题目描述

贝茜在和约翰玩一个“捉迷藏”的游戏。她正要找出所有适合她躲藏的安全牛棚。

一共有 nn 个牛棚,被编为 11 到 nn 号。她知道约翰(捉牛者)从牛棚 11 出发。

所有的牛棚由 mm 条双向路连接,每条双向路连接两个不同的牛棚。

所有的牛棚都是相通的,贝茜认为同牛棚 11 距离最远的的牛棚是安全的。

两个牛棚间的距离是指,从一个牛棚到另一个牛棚最少需要通过的道路数量。

请帮贝茜找出所有的安全牛棚。

输入格式

第1行输入两个整数 nn 和 mm ,之后 mm 行每行输入两个整数,表示一条路的两个端点。

输出格式

仅一行,输出三个整数。

第 11 个表示安全牛棚(如果有多个,输出编号最小的)。

第 22 个表示牛棚 11 和安全牛棚的距离。

第 33 个表示有多少个安全的牛棚。

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

题目来源

Silver

数据规模与约定

对于 100%100 \% 的数据 1≤n≤2∗1041 \le n \le 2*10^4,1≤m≤5∗1041 \le m \le 5*10^4。