Bear and Chase

题意翻译

一张 $n$ 个点，$m$ 条边的简单无向连通图。B有一个神奇的探测器：BCD。当B在某个点使用BCD时，BCD会显示A所在点与B所在点之间的距离（即最短路所经过的边数）。B只有两天的时间捉拿A，具体过程如下： 1.第一天，A随机潜伏在某个点，即A位于每个点的概率都是 $ \frac1n $ 。B将挑选一个点 a ，在 a 处使用BCD，得知A所在点与 a 的距离。然后B可以选择立刻调查某个点：如果A正好位于被调查的点，则B成功地将A捉拿归案（如果A刚好位于点 a ，那么BCD会显示 0 ，显然B直接调查点 a 就能直接将A捉拿归案）；否则，A会意识到自己正被追查，导致B的任务直接失败！ 2.如果第一天没有立刻调查。那么在夜里，A会随机选择一个与A所在点相邻的点，并前往该点。即如果有 d 个点与A所在点相连，则A有 $\frac1d$ 的概率前往其中的每个点。 3.第二天，B将挑选一个点 b ，在 b 处使用BCD（忽略B从 a 前往 b 的时间），得知A所在点与 b 的距离。然后B必须选择一个点进行调查。如果A刚好位于被调查的点，则B成功的将A捉拿归案；否则，B的任务失败。 现在，请你帮助B，制定合适的追捕计划，选择前往调查的点，使得B将A捉拿归案的概率最大。输出这个最大的概率。

题目描述

Bearland has $ n $ cities, numbered $ 1 $ through $ n $ . There are $ m $ bidirectional roads. The $ i $ -th road connects two distinct cities $ a_{i} $ and $ b_{i} $ . No two roads connect the same pair of cities. It's possible to get from any city to any other city (using one or more roads). The distance between cities $ a $ and $ b $ is defined as the minimum number of roads used to travel between $ a $ and $ b $ . Limak is a grizzly bear. He is a criminal and your task is to catch him, or at least to try to catch him. You have only two days (today and tomorrow) and after that Limak is going to hide forever. Your main weapon is BCD (Bear Criminal Detector). Where you are in some city, you can use BCD and it tells you the distance between you and a city where Limak currently is. Unfortunately, BCD can be used only once a day. You don't know much about Limak's current location. You assume that he is in one of $ n $ cities, chosen uniformly at random (each city with probability ). You decided for the following plan: 1. Choose one city and use BCD there. - After using BCD you can try to catch Limak (but maybe it isn't a good idea). In this case you choose one city and check it. You win if Limak is there. Otherwise, Limak becomes more careful and you will never catch him (you loose). 2. Wait $ 24 $ hours to use BCD again. You know that Limak will change his location during that time. In detail, he will choose uniformly at random one of roads from his initial city, and he will use the chosen road, going to some other city. 3. Tomorrow, you will again choose one city and use BCD there. 4. Finally, you will try to catch Limak. You will choose one city and check it. You will win if Limak is there, and loose otherwise. Each time when you choose one of cities, you can choose any of $ n $ cities. Let's say it isn't a problem for you to quickly get somewhere. What is the probability of finding Limak, if you behave optimally?

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ m $ ( $ 2<=n<=400 $ , ) — the number of cities and the number of roads, respectively. Then, $ m $ lines follow. The $ i $ -th of them contains two integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i},b_{i}<=n $ , $ a_{i}≠b_{i} $ ) — cities connected by the $ i $ -th road. No two roads connect the same pair of cities. It's possible to get from any city to any other city.

输出格式

Print one real number — the probability of finding Limak, if you behave optimally. Your answer will be considered correct if its absolute error does not exceed $ 10^{-6} $ . Namely: let's assume that your answer is $ a $ , and the answer of the jury is $ b $ . The checker program will consider your answer correct if $ |a-b|<=10^{-6} $ .

输入输出样例

输入样例 #1

3 3
1 2
1 3
2 3

输出样例 #1

0.833333333333

输入样例 #2

5 4
1 2
3 1
5 1
1 4

输出样例 #2

1.000000000000

输入样例 #3

4 4
1 2
1 3
2 3
1 4

输出样例 #3

0.916666666667

输入样例 #4

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

输出样例 #4

0.900000000000

说明

In the first sample test, there are three cities and there is a road between every pair of cities. Let's analyze one of optimal scenarios. 1. Use BCD in city $ 1 $ . - With probability  Limak is in this city and BCD tells you that the distance is $ 0 $ . You should try to catch him now and you win for sure. - With probability  the distance is $ 1 $ because Limak is in city $ 2 $ or city $ 3 $ . In this case you should wait for the second day. 2. You wait and Limak moves to some other city. - There is probability  that Limak was in city $ 2 $ and then went to city $ 3 $ . -  that he went from $ 2 $ to $ 1 $ . -  that he went from $ 3 $ to $ 2 $ . -  that he went from $ 3 $ to $ 1 $ . 3. Use BCD again in city $ 1 $ (though it's allowed to use it in some other city). - If the distance is $ 0 $ then you're sure Limak is in this city (you win). - If the distance is $ 1 $ then Limak is in city $ 2 $ or city $ 3 $ . Then you should guess that he is in city $ 2 $ (guessing city $ 3 $ would be fine too). You loose only if Limak was in city $ 2 $ first and then he moved to city $ 3 $ . The probability of loosing is . The answer is .