선인장 그래프 간선 지우기

선인장 그래프는 서로 다른 두 단순 사이클이 정점을 많아야 한 개 공유하는 연결 무향 그래프이다. 단순 사이클은 같은 정점을 두 번 지나지 않는 사이클을 뜻한다. 선인장 그래프에서는 그런 사이클 두 개가 정점 두 개 이상에서 겹치지 않는다.

주어진 선인장 그래프에서 게임을 한다. 한 단계마다 남아 있는 간선 중 하나를 골라 지운다. 지울 간선은 남아 있는 간선 전체에서 균등한 확률로 고르고, 각 단계의 선택은 서로 독립이다. 그래프가 더 이상 연결되어 있지 않으면, 즉 사이에 경로가 하나도 없는 두 정점이 생기면 게임이 끝난다.

게임이 끝날 때까지 거치는 단계 수의 기댓값을 구하시오.

첫째 줄에 정점의 수 $n$과 간선의 수 $m$이 주어진다. ($1 \le n \le 600$, $1 \le m \le n(n-1)/2$) 그래프의 정점에는 $1$번부터 $n$번까지 번호가 붙어 있다.

다음 $m$개 줄에는 줄마다 서로 다른 두 정수 $a$와 $b$가 주어진다. ($1 \le a, b \le n$) 정점 $a$와 정점 $b$를 잇는 간선이 있다는 뜻이다.

두 정점을 잇는 간선은 많아야 한 개이고, 입력으로 주어지는 그래프는 문제에서 설명한 선인장 그래프이다.

게임이 끝날 때까지 거치는 단계 수의 기댓값을 한 줄에 출력한다. 소수점 아래 여섯째 자리까지 반올림하고, 소수점 아래 자리를 정확히 여섯 개 출력한다.