该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P2951 [USACO09OPEN] Hide and Seek S

题目描述

给定一个有 $n$ 个点、$m$ 条边（每条边边权为 $1$）的无向图，求从 $1$ 号点到所有点的距离中：

• 最短路径长度最长的点的编号（如有多个则输出最小编号）$x$。
• 最长最短路径的长度 $S$。
• 有多少个点离 $1$ 号点的最短距离 为 $S$，设为 $K$。

输入格式

第一行两个整数 $n \ m \ (2 \le n \le 20000,1 \le m \le 50000)$。

下来 $m$ 行，每行两个整数 $x_i \ \ y_i$ ，表示一条无向边。

输出格式

一行三个整数 $x \ S \ K$，两两中间空格隔开。

输入输出样例 #1

输入 #1

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

输出 #1

4 2 3

说明/提示

这里谷仓4，5，6距离1号谷仓都是2，但是4编号最小所以输出4.因此最远距离是2且有3个谷仓，依次输出：2和3。