2887 - 最远的点

题目描述

N 个点(编号为 1 \sim N),M 条边构成的无向图。

请编程计算出:

  1. 1 号点最远的点(距离 1 号点最短路的最大值对应的点)是哪个点,输出其编号,如果有多个最远的点,请输出编号最小的点。

  2. 该点距离 1 号点的最远距离是多少。(最短路的最大值)

  3. 有多少个点是距离 1 号点最远的点。

输入

1 行读入两个整数 N,M

接下来 M 行每行读入两个整数 u,v ,表示点 u,v 之间有一条无向边。

输出

输出 3 个整数,用空格隔开,分别表示:距离 1 号点最远点的编号(如果有多个,输出编号最小的)、最远点的距离、有几个最远的点。

样例

输入

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

输出

4 2 3 
说明

数据 1 说明

6 个点,7 条边,离 1 号点最远的点有 3 个,分别是点 4,5,6。最远距离是 2

数据范围

对于 100\% 的测试数据, 2 \le N \le 200001 \le M \le 500001 \le u,v \le N,且 u \neq v

测试数据保证从 1 号点可以到达其他所有的点。

来源

东方博宜OJ

标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 173
通过人数 92
金币数量 1 枚
难度 入门


上一题 下一题