네트워크 신뢰도

시간 제한3초메모리 제한512 MB

요약

무방향 그래프의 각 간선이 같은 확률로 독립적으로 사라질 때, 남은 그래프가 연결되어 있을 확률을 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 비트 연산, 확률, 그래프
정답자: 아직 제출이 없습니다

문제

무방향 그래프가 주어진다. 각 간선은 일정한 확률로 사라진다. 남은 그래프가 연결되어 있을 확률을 구하라.

입력

첫째 줄에 세 정수 $N$ ( $1 \leq N \leq 14$ ), $M$ ( $0 \leq M \leq 100$ ), $P$ ( $0 \leq P \leq 100$ )가 공백 하나를 사이에 두고 주어진다. $N$ 은 정점의 수, $M$ 은 간선의 수다. $P$ 는 백분율로 나타낸 확률이다.

다음 $M$ 개의 줄에 간선이 주어진다. 각 줄에는 두 정수 $v_i$ 와 $u_i$ ( $1 \leq u_i, v_i \leq N$ )가 주어진다. ( $u_i, v_i$ )는 두 정점 $u_i$ 와 $v_i$ 를 잇는 간선을 나타낸다.

출력

남은 그래프가 연결되어 있을 확률을 한 줄에 출력한다. 소수점 아래 자릿수는 얼마든지 좋다. 다만 절대 오차는 $10^{-9}$ 이하여야 한다.

예제3

예제 1
입력
```
3 3 50
1 2
2 3
3 1
```
예상 출력
```
0.500000000000
```
예제 2
입력
```
3 3 10
1 2
2 3
3 1
```
예상 출력
```
0.972000000000
```

예제 3

입력

예상 출력

0.437500000000