Ticket Completed?

문제

Many are familiar with the board game Ticket To Ride (Ticket To Ride is copyrighted by Days of Wonder, Inc.) where players compete to build a railway empire, claiming routes between cities. The game consists of a map of cities and various rail segments each connecting two adjacent cities. 

A key way to score points towards winning the game is to complete Destination Tickets.  Each ticket specifies two distinct cities. A player earns the points that are indicated on the ticket if they have claimed one or more rail segments that form a path connecting the two cities.

There is one ticket for each distinct unordered pair of cities. In our version of the game, each player is randomly given a ticket and they have an equal probability of receiving any ticket. Given a list of rail segments you have already claimed, determine the probability you earn points from the ticket you are given.

입력

The first line of input contains two integers $NN$ ($2\le N\le {10}^{5}2\; \backslash leq\; N\; \backslash leq\; 10^5$), which is the number of cities, and $MM$ ($0\le M\le {10}^{6}0\; \backslash leq\; M\; \backslash leq\; 10^6$), which is the number of rail segments you have claimed.

The next $MM$ lines describe your claimed rail segments. Each line contains two distinct integers $ii$ ($1\le i\le N1\; \backslash leq\; i\; \backslash leq\; N$) and $jj$ ($1\le j\le N1\; \backslash leq\; j\; \backslash leq\; N$), which are the cities that this rail segment connects.

출력

Display the probability you earn points from the ticket you are given.

Your answer should have an absolute error of at most ${10}^{-6}10^\{-6\}$.

4 2
1 2
3 4

0.33333333333333333333

5 4
1 5
2 3
2 4
3 4

0.4

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

0.42857142857142857143