Alliances
In the Triametist Kingdom, there are n cities and m roads connecting some of them. One day, due to an experiment by the court magician D, a mysterious event occurred: the kingdom split into multiple copies, or reflections, across the universe. In each reflection, every road was enchanted in either an alpha or omega manner. Notably, every possible combination of road enchantments appeared in exactly one of these reflections.
The enchantments have a special property: cities a, b, and c form a trade union if and only if there are roads connecting a to b, b to c, and c to a, all enchanted in the same way.
Input
The first line of the input provides two integers, n and m, representing the number of cities and roads in the Triametist Kingdom. The following m lines each contain a pair of numbers, indicating the cities connected by each road. The constraints are 3 ≤ n ≤ 20000 and 1 ≤ m ≤ 500000. No two cities are connected by more than one road, and no road connects a city to itself.
Output
Output a single real number with the highest possible precision, representing the average number of trade unions formed across all reflections of the Triametist Kingdom.