Expected Defense Cost

In this problem the Earth’s defense network is modeled as a simple undirected cactus graph \(G(V,E)\) with \(n\) nodes and \(m\) edges. A cactus graph is one in which each vertex is contained in at most one simple cycle.

During each alien attack, a set \(S \subseteq V\) of defense nodes is randomly chosen (each subset is equally likely). To start the defense network for this attack, an energy connection subnetwork is activated in which some edges \(H(S) \subseteq E\) are selected so that:

1. Connectivity: In the new graph \(G'(V, H(S))\) the nodes in \(S\) are connected.
2. Minimality: Among all edge subsets ensuring connectivity, \(H(S)\) has the minimum number of edges. (In other words, \(H(S)\) is the Steiner tree connecting \(S\) in \(G\) if we judge the cost solely by the number of edges.)

Recall that if \(|S| \le 1\) we define the cost \(|H(S)| = 0\), and if \(|S| \ge 2\) then one must add at least some edges (possibly via intermediate vertices not in \(S\)) to connect all chosen nodes. For example, if \(G\) is a tree then for any \(S\) the unique minimal subtree connecting \(S\) has a cost equal to the sum of the distances (number of edges) along the unique paths joining them.

Your task is to compute the expected cost of activating the defense subnetwork:

[ E = \frac{1}{2^{|V|}} \sum_{S \subseteq V} |H(S)| ]

Note: Although the graph structure (possibly a cycle or a tree‐like structure) might influence the individual Steiner tree cost, you may assume that \(n\) is small so that a solution based on enumerating all subsets \(S\) is feasible. In particular, you can compute the cost for each nonempty subset \(S\) as follows:

• First, precompute the shortest distance \(d(u,v)\) (in number of edges) between any two nodes \(u\) and \(v\) in \(G\) (using, for example, a BFS from each vertex). (It is guaranteed that \(G\) is connected.)
• For a subset \(S\) with \(|S| \ge 2\), construct the complete graph on the nodes of \(S\) with edge weights \(d(u,v)\), and compute the weight of a minimum spanning tree (MST) on that complete graph. This weight is exactly \(|H(S)|\).

Output the expected cost. Your answer will be accepted if its absolute or relative error does not exceed \(10^{-6}\).

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) where \(1 \le n \le 15\) and \(n-1 \le m \le n+\text{(at most one extra edge per cycle)}\). Each of the next \(m\) lines contains two integers \(u\) and \(v\) (1-indexed) representing an edge between nodes \(u\) and \(v\). It is guaranteed that \(G\) is connected and that it is a cactus graph (each node lies on at most one simple cycle).

outputFormat

Output a single number — the expected cost (i.e. the average value of \(|H(S)|\) over all \(2^n\) subsets \(S \subseteq V\)). The answer will be accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

3 2
1 2
2 3

0.75