무작위 신장 트리

시간 제한1초메모리 제한1024 MB

요약

간선 가중치가 0과 1 사이의 균등 분포를 따를 때, 기댓값인 최소 신장 트리의 가중치를 기약분수 p/q로 구합니다.

난이도: 어려움10점 중 8점
유형: 최소 신장 트리, 수학, 조합론, 그래프
정답자: 아직 제출이 없습니다

문제

유우카는 모에 국에 살고 있다. 모에 국의 도로망은 연결된 그래프 $G$ 이다. 각 간선의 길이는 $[0, 1]$ 구간에서 균등하게 뽑은 실수이다. 유우카는 $G$ 의 최소 신장 트리 길이의 기댓값을 알고 싶어 한다.

입력

첫 줄에 정점의 개수 $n$ 과 간선의 개수 $m$ 이 주어진다 ( $2 \le n \le 8$ , $n - 1 \le m \le \frac{n(n-1)}{2}$ ). 정점에는 $1, 2, \dots, n$ 의 번호가 붙어 있다. 이어지는 $m$ 개의 줄에는 정점 $a_i$ 와 $b_i$ 를 잇는 간선이 각각 하나씩 주어진다 ( $1 \le a_i, b_i \le n$ ). 그래프는 연결되어 있으며, 자기 자신으로 가는 간선과 중복 간선은 없다.

출력

기댓값을 분수 $p/q$ 꼴로 한 줄에 출력한다.

예제2

예제 1
입력
```
3 2
1 2
2 3
```
예상 출력
```
1/1
```
예제 2
입력
```
3 3
1 2
2 3
3 1
```
예상 출력
```
3/4
```