测试数据来自 system/1650

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　某城市有 \(n\) 个居民点，它们被编号为 \(1\sim n\)，有 \(m\) 条双向道路，每条道路连接不同的两个居民点，且所有的道路长度都是 1。

　　市政府在 1 号和 \(n\) 号居民点各设立了一个消防队，如果某处居民点发生火灾，距离最近的消防队会通过城市道路沿最近的路线尽快到达火灾地点。

　　现在政府想知道，城市中距离消防队最远的居民点是哪个？这里的最远是指距离消防站最大的最短路线。如果有多个这样的居民点，请输出编号最小的；同时还要输出这个最远距离是多少，和有几个这样的居民点距离消防队那么远。

【输入格式】

　　第一行包含两个整数 \(n,\ m\)，分别表示居民点的数目和城市道路数目。
　　接下来的 \(m\) 行，每行两个整数：\(u\ v\)，表示居民点 \(u\) 和 \(v\) 间有一条双向道路。

【输出格式】

　　仅一行，三个整数，两两中间空格隔开。分别表示距离第消防队最远的居民点编号（如有多个则输出编号最小的）；以及最远的距离，和有几个居民点距离消防队居民点那么远。

【输入输出样例】

　Input

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

　Output

4 2 2

【输入输出样例解释】

　　这里居民点4，5距离消防队都是2，但是4编号最小所以输出4。因此最远距离是2且有2个居民点。

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤n≤20000\)，\(1≤m≤50000\)。

【来源】

　　Mr.he