开始 2019-11-09 13:30:00

CSP-S赛前信心赛day1

结束 2019-11-09 17:00:00
Contest is over.
当前 2020-06-05 19:47:45

A. 游客

描述

有一个城市,由$n$个路口与$m$条道路构成,每条道路都是一样长的,现在你需要选择一个路口派送城市的旅游地图给路过的游客, 一条道路如果是安全的, 那么这条道路的两端的某个路口应该恰好是你选择的那个路口.

对于一条从$1$到$n$的最短路径,如果中间经过了你选取的路口而且这个路口不是起点和终点,那么就会有两条道路是安全的.

对于所有从$1$到$n$的最短路径, 你选取的路口应该可以使得平均的安全道路的数量最大

求出这个最大的平均值
 

输入

第一行输入两个整数$n,m$ 表示路口与道路的数量

($2 \le n \le 100, n - 1 \le m \le n*(n-1) / 2$)

接下来$m$ 行每行两个整数$u, v$ 表示一条双向道路 $1 \le u, v\le n$

保证没有重边而且任意两个路口是可达的

输出

输出一个浮点数,误差不超过$10^{-6}$

样例

输入

4 4
1 2
2 4
1 3
3 4

输出

1.000000000000

输入

11 14
1 2
1 3
2 4
3 4
4 5
4 6
5 11
6 11
1 8
8 9
9 7
11 7
1 10
10 4

输出

1.714285714286

提示

对于30%的数据: $2 \le n \le 10$

对于60%的数据: $2\le n \le 15$

对于100%的数据: $2\le n \le 100$
 

时间限制 1 秒
内存限制 256 MB