Woburn Challenge 2015-16 Round 2 - Senior Division

Obi-Wan Kenobi and Anakin Skywalker, once the best of friends, find themselves about to have a vicious duel on a volcanic planet in the Mustafar system. Their fight will take place in the Separatists' hideout, a base consisting of ~N~ ~(2 \le N \le 45\,678)~ chambers and ~M~ ~(0 \le M \le 234\,567)~ corridors. The ~i~-th corridor connects chambers ~A_i~ and ~B_i~, and can be traversed in either direction. No pair of chambers are directly connected by multiple corridors.

There's just one hold up – Obi-Wan and Anakin must find each other first. Anakin is waiting in a random chamber, and Obi-Wan is similarly about to land in a random chamber. With each of these locations chosen uniformly at random from the set of possible chambers, there are ~N^2~ possible, equally-likely ordered pairs of starting chambers.

As soon as Obi-Wan lands in his chamber, he and Anakin will start looking for one another. Exactly once every minute, each of them will travel along a random corridor connected to their current chamber (chosen uniformly at random from the set of such corridors), unless their current chamber isn't connected to any corridors, in which case they'll stay where they are. If the two of them find themselves in the same chamber during any given minute, they'll commence their duel. Otherwise, they'll continue this process infinitely (Jedi do live for a long time). Note that, with the power of the Force, they each travel through their chosen corridor extremely quickly every minute – therefore, they can never meet up in a corridor, even if they both travel through the same one at the same time (in opposite directions).

What's the probability that Obi-Wan and Anakin will eventually meet up and actually have their duel?

In cases worth ~40\%~ of the points, ~N \le 1\,234~ and ~M \le 4\,567~.
In a subset of those cases worth ~20\%~ of the points, ~N \le 34~ and ~M \le 456~.

Input Specification

The first line of input consists of two space-separated integers ~N~ and ~M~.
The next ~M~ lines each consist of two space-separated integers ~A_i~ and ~B_i~, for ~1 = 1 \dots M~.

Output Specification

Output a single real number between ~0~ and ~1~, the probability that Obi-Wan and Anakin will eventually duel.
Your answer must have an absolute error of no more than ~10^{-6}~.

Sample Input

6 7
2 3
2 4
2 5
3 4
3 5
4 5
6 1

Sample Output

0.5

Explanation

There are ~36~ possible, equally-likely ordered pairs of starting chambers for Obi-Wan and Anakin. It so happens that for ~18~ of them, the probability of an eventual encounter is ~100\%~ (including the pairs ~(1, 1)~ and ~(2, 4)~), while for the other ~18~, it's ~0\%~ (including the pairs ~(1, 6)~ and ~(5, 6)~).