31352번 - Random Spanning Tree 다국어

문제

Yuuka lives in Moe Country. The road system in Moe Country is a connected graph $G$. Each edge has a random (real) length, which is uniformly random in $[0, 1]$.

Now Yuuka is eager to know the expectation of minimum spanning tree of $G$.

입력

The first line contains 2ドル$ integers $n, m,ドル which denotes the number of vertices and edges of $G,ドル respectively (2ドル \leq n \leq 8, n - 1 \leq m \leq \frac{n(n - 1)}{2}$).

The vertices in $G$ are conveniently labeled by 1,ドル 2, \dots, n$.

Each of the following $m$ lines contains 2ドル$ integers $a_i, b_i,ドル which denotes an edge between vertices $a_i$ and $b_i$ (1ドル \leq a_i, b_i \leq n$).

It is guaranteed that the graph $G$ is connected, without self loops and parallel edges.

출력

A single fraction $p/q$ denotes the expectation.

제한

힌트