P4517 [JSOI2018] Defense Network

Although the attack plan of the aliens has been obtained, ``JYY`` unexpectedly finds that the alien mothership attacks Earth randomly. A defense network must be deployed on Earth as soon as possible to resist the mothership’s attack. The defense network on Earth consists of nodes and energy links between nodes. The defense network can be regarded as a simple undirected graph $G(V, E)$ with $n$ vertices and $m$ edges. Each defense node corresponds to a vertex in $V$, and each energy link corresponds to an edge in $E$. In addition, considering energy transmission efficiency when building the defense network, in $G$ each vertex belongs to at most one simple cycle. Since the mothership’s attack is random, at the beginning of each attack, ``JYY`` will choose some defense nodes $S \subseteq V$ according to the current attack and use energy links to connect these defense nodes to activate a defense subnetwork. In other words, ``JYY`` will choose a subset of edges $H(S) \subseteq E$ in $G$, which satisfies: 1. (Defense subnetwork connected) If we build a new graph $G'(V, H(S))$, i.e., connect the vertices in $G$ with the edges in $H(S)$, then for any selected defense vertices $x, y \in S$, they are connected in $G'$. 2. (Defense subnetwork minimal) Subject to condition 1 (defense subnetwork connected), the number of selected edges is minimal, i.e., $\vert H(S)\vert$ is minimal. $H(S)$ is the Steiner tree generated by the set $S$ in graph $G$, and $\vert H(S)\vert$ is the minimal cost to activate the defense subnetwork. Considering the randomness of the mothership’s attack, ``JYY`` wants you to compute the expectation of the activation cost: $$\frac{1}{2^{\vert V\vert}}\sum_{S\subseteq V}\vert H(S)\vert.$$

The first line contains two integers $n, m$, denoting the number of vertices and edges in the graph. The next $m$ lines each contain two integers $u, v$ $(1 \le u, v \le n)$, representing an edge. The input guarantees no self-loops or multiple edges, and that each vertex belongs to at most one simple cycle.

Output one line: the expected cost to activate the defense subnetwork. Suppose the expectation is written in irreducible fraction form $P/Q$. Output the remainder of $P \cdot Q^{-1} \text{ mod 1,000,000,007}$, where $Q^{-1}$ is the unique integer satisfying $Q \cdot Q^{-1} \equiv \text{1 (mod 1,000,000,007)}$.

Sample explanation. Sample 1 is a path and includes the following cases: 1. $\{\}, \{1\}, \{2\}, \{3\}, \vert H(S)\vert = 0$. 2. $\{1, 2\}, \{2, 3\}, \vert H(S)\vert = 1$. 3. $\{1, 3\}, \{1, 2, 3\}, \vert H(S)\vert = 2$. Therefore $P/Q = 3/4$, $P \cdot Q^{-1} = 750,000,006$. In sample input 2, $\sum_{S\subseteq V}\vert H(S)\vert = 174$, thus $P/Q = 87/32$, $P \cdot Q^{-1} = 468,750,006 \text{ mod 1,000,000,007}$. Constraints - For 20% of the testdata, $1 \le n \le 8$. - For 40% of the testdata, $1 \le n \le 20$. - For 100% of the testdata, $1 \le n \le 200$. Translated by ChatGPT 5