Problem description

Dany jest graf nieskierowany. W każdym kroku losowane są dwa różne wierzchołki tego grafu (z jednostajnym prawdopodobieństwem) i łączone są krawędzią. Proces zakończy się, gdy graf stanie się spójny.

Napisz program, który: wczyta graf, wyznaczy oczekiwaną wartość liczby kroków do zakończenia procesu (uzyskania spójnego grafu) i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i M, oddzielone pojedynczym odstępem i określające liczbę wierzchołków oraz liczbę krawędzi. W kolejnych M wierszach znajdują się opisy krawędzi, po jednej w wierszu. Opis każdej krawędzi zawiera dwie liczby u i v, określające numery wierzchołków grafu, które są już połączone krawędzią.

Wierzchołki grafu numerowane są kolejnymi liczbami naturalnymi od 1 do N włącznie.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba rzeczywista – wartość oczekiwaną liczby krawędzi, które należy dodać do grafu, zgodnie z powyższymi zasadami, aby graf stał się spójny.

Odpowiedź zostanie zaakceptowana, jeśli będzie się różnić od poprawnej o co najwyżej 10⁻⁶.

Ograniczenia

1 ≤ N ≤ 40, 1 ≤ M ≤ 1 000.

Przykład

4 2
1 2
3 4

1.500000000