# Problem D

Ticket Completed?

Many are familiar with the board game Ticket To Ride^{1} 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.

## Input

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

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

## Output

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

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

Sample Input 1 | Sample Output 1 |
---|---|

4 2 1 2 3 4 |
0.33333333333333333333 |

Sample Input 2 | Sample Output 2 |
---|---|

5 4 1 5 2 3 2 4 3 4 |
0.4 |

Sample Input 3 | Sample Output 3 |
---|---|

7 5 1 2 2 3 3 4 5 6 6 7 |
0.42857142857142857143 |

**Footnotes**

- Ticket To Ride is copyrighted by Days of Wonder, Inc.