人活着系列之交通安全

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

涛涛不尽的似水光阴,足以引出世间的万千苦难,在你一放手,一转身的一刹那,有些事情会完全改变。太阳落山了,当它第二天重新升起来时,有些人,有些事,也许都会跟你永远分开了。人生在世好像过眼烟云,一代过去,一代又来,其实都是捕风,其实都是捉影,能留住什么呢?然而,我们的安全却是必须要得到保障的!
Sky Island是一个漂浮在空中的美丽王国,它是地球与宇宙中其他生命交流的窗口。所以王国中生活着各色各样的“人”。
Sky Island 的路网是由n个城市,m条双向道路组成。由于国王是一个大魔法师,所以不管路有多长总是一个单位时间就可以走完这一条路。(当然一个单位时间可以做许多事情的)
在这n个城市中,标号为1的城市里有Sky Island前往地球的港口,标号为n的城市是外星生命来到Sky Island着陆的地方。也就是说如果外星生命想去地球。需要先降落到城市n,然后去城市1,然后在搭乘统一的交通工具去地球。当然了旅客们都是很急的,他们总是想在城市1与城市n之间的旅行消耗最少的时间。也就是所他们总是选择最短路。
由于“人口”混杂不利于管理。国王决定在某一个城市设立警察局来保证外星生命在城市1与城市n之间旅行过程中的安全。已知若某个城市设立警察局的话,与它相连的所有道路都是安全的。也就是说若某条道路两端连接的城市里的任意一个都没有警察局的话,这条道路就是危险的。
对于任意一条最短路,我们定义一个特征值K=(在安全道路的条数)/最短路的总条数。因为只能设立一个警察局,国王想知道怎样可以使这个警察局的产生效果最大化。也就是说怎样能使所有最短路的特征值的最大。

Input

输入为多组,到文件结束。

每一组第一行两个数n,m

紧接m行每行 u,v

城市数不大于100,没有重复边。

Output

 对于每组数据输出一行一个浮点数为特征值的最大平均值。输出保留三位小数。

Sample Input

5 5
3 2
2 1
4 3
4 1
5 3

Sample Output

2.000

Hint

 

Source

lin