Interconnect

In the Kingdom of Lipshire there are $n$ towns. Some of the old roads have fallen into such disrepair that they can no longer be used, so the kingdom has decided to rebuild its road network.

The new road network must interconnect every town: there must be a path between any two towns.

The road administration can build exactly one road per year, but the builders are completely out of control. No matter what orders they are given, each year they choose two distinct towns $a$ and $b$ uniformly at random among all $\binom{n}{2}$ unordered pairs and build a road between them — even if those towns are already directly or indirectly connected. Every pair is equally likely. A traveler can enter or leave each road only at its two endpoint towns, and every road is bidirectional.

Given the towns that are still joined by the good roads that remain, determine the expected number of years until the whole road network becomes interconnected.

The first line contains two integers $n$ and $m$ ($2 \le n \le 30$, $0 \le m \le 1000$) — the number of towns and the number of good roads that still remain. Towns are numbered from $1$ to $n$.

Each of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$) describing a remaining road between towns $u_i$ and $v_i$. There may be several roads between the same pair of towns, but no road connects a town to itself.

The expected number of years is always a rational number. Output it as an exact reduced fraction in the form p/q, where $q \ge 1$, $\gcd(p, q) = 1$, and the fraction equals the expected number of years. If the road network is already interconnected, the expected value is $0$ and must be printed as 0/1.

For example, an expected value of $\tfrac{3}{2}$ is printed as 3/2, and an expected value of $1$ is printed as 1/1.