|Codeforces Round #356 (Div. 1)|
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:
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.
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.
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 .