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.