CF679D.Bear and Chase

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?

Bearland 有 $n$ 座城市，编号为 $1$ 到 $n$。共有 $m$ 条双向道路。第 $i$ 条道路连接两个不同的城市 $a_i$ 和 $b_i$。任意一对城市之间至多只有一条道路相连。任意两座城市之间均可通过一条或多条道路相互到达（即图是连通的）。

城市 $a$ 与 $b$ 之间的距离定义为从 $a$ 到 $b$ 所需经过的最少道路数。

Limak 是一只灰熊。他是一名罪犯，而你的任务是抓捕他（或至少尝试抓捕他）。你仅有两天时间（今天和明天），之后 Limak 将永远隐藏起来。

你最主要的武器是 BCD（熊类罪犯探测器）。当你身处某座城市时，可使用一次 BCD，它将告诉你：你所在城市与 Limak 当前所在城市之间的距离。不幸的是，BCD 每天最多只能使用一次。

你对 Limak 当前的位置知之甚少。你假设他等概率地随机出现在 $n$ 座城市中的任意一座（即每座城市的概率均为 ）。你制定了如下计划：

1. 选择一座城市并在该城市使用 BCD。
   • 使用 BCD 后，你可以立即尝试抓捕 Limak（但也许这并非明智之举）。此时你选择一座城市进行搜查；若 Limak 正好在此城市，则你获胜；否则，Limak 将变得更加警觉，你将永远无法再抓住他（你失败）。
2. 等待 24 小时后再次使用 BCD。你知道 Limak 在此期间会更换位置。具体而言，他将从初始所在城市出发，等概率地随机选择一条与其所在城市相连的道路，并沿该道路移动到另一座城市。
3. 明天，你再次选择一座城市并在该城市使用 BCD。
4. 最后，你将尝试抓捕 Limak：你选择一座城市进行搜查；若 Limak 正好在此城市，则你获胜；否则你失败。

每次你选择城市时，均可从 $n$ 座城市中任选其一。我们假定你能迅速抵达任意城市，因此移动时间不构成限制。

若你采取最优策略，成功找到 Limak 的概率是多少？

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.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 400$，），分别表示城市的数量和道路的数量。

接下来有 $m$ 行。其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i,\,b_i \leq n$，且 $a_i \ne b_i$），表示第 $i$ 条道路所连接的两座城市。

任意一对城市之间至多只有一条道路相连。任意一座城市均可通过道路到达其他任意一座城市。

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.

输出一个实数——即在你采取最优策略时找到 Limak 的概率。若你的答案绝对误差不超过 $10^{-6}$，则视为正确。

具体而言：假设你的答案为 $a$，评测组的答案为 $b$。当且仅当 $|a - b| \leq 10^{-6}$ 时，评测程序将判定你的答案正确。

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 .

在第一个样例测试中，共有三座城市，且每对城市之间都有一条道路。我们来分析其中一种最优策略。

1. 在城市 1 使用 BCD。
   • 以概率 Limak 当前就在该城市，BCD 显示距离为 0。此时你应立即尝试抓捕他，从而确保获胜。
   • 以概率 距离为 1，因为 Limak 位于城市 2 或城市 3。此时你应等待第二天。
2. 你选择等待，Limak 将移动至另一座城市。
   • 有概率 Limak 原本在城市 2，随后移动到了城市 3。
   • 他从城市 2 移动到了城市 1。
   • 他从城市 3 移动到了城市 2。
   • 他从城市 3 移动到了城市 1。
3. 再次在城市 1 使用 BCD（当然也可以选择在其他城市使用）。
   • 若测得距离为 0，则可确定 Limak 就在此城市（你获胜）。
   • 若测得距离为 1，则 Limak 位于城市 2 或城市 3。此时你应猜测他在城市 2（猜测城市 3 同样可行）。

你仅会在以下情形失败：Limak 初始位于城市 2，随后移动至城市 3。失败的概率为 。答案为 。