题目描述

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

一共有 $n$ 个牛棚，被编为 $1$ 到 $n$ 号。她知道约翰（捉牛者）从牛棚 $1$ 出发。

所有的牛棚由 $m$ 条双向路连接，每条双向路连接两个不同的牛棚。

所有的牛棚都是相通的，贝茜认为同牛棚 $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

题目来源

Silver

数据规模与约定

对于 $100 \%$ 的数据 $1 \le n \le 2*10^4$，$1 \le m \le 5*10^4$。