커버 타임
시간 제한8초메모리 제한512 MB
연결된 무방향 그래프에서 정점 1에서 출발한 무작위 보행이 모든 정점을 방문할 때까지 걸리는 기대 걸음 수를 계산한다. 정점 수는 최대 10이다.
문제
정점이 1번부터 N번까지 번호가 붙은 연결 무방향 그래프 G가 있다. G는 단순 그래프, 즉 자기 자신으로 향하는 간선이나 평행 간선이 없다.
G의 정점 위를 걷는 입자 P가 있다. 처음에 P는 정점 1에 있다. 각 단계에서 P는 인접한 정점 중 하나로 이동한다. 인접한 정점이 여러 개라면 각 정점은 같은 확률로 선택된다.
커버 타임은 P가 모든 정점을 방문하는 데 필요한 걸음 수의 기댓값이다.
주어진 각 그래프 G에 대해 커버 타임을 계산하는 것이 과제이다.
입력
입력은 다음과 같은 형식으로 주어진다.
N M
a1 b1
.
.
.
aM bM
N은 정점의 수, M은 간선의 수이다. 2 ≤ N ≤ 10이라 가정할 수 있다. ai와 bi (1 ≤ i ≤ M)는 i번째 간선이 연결하는 두 정점을 나타내는, N 이하인 양의 정수이다. 입력은 문제 설명에 적힌 조건, 즉 주어진 그래프 G가 연결 단순 그래프라는 조건을 만족한다고 가정할 수 있다.
출력
커버 타임을 한 줄에 출력한다.
답은 소수점 아래 여섯 자리까지 출력해야 하며, 오차가 10-6보다 크면 안 된다.