#2547. 「JSOI2018」防御网络

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: diamond_duke

题目描述

虽然成功得到了外星人的进攻计划,但 JYY 意外地发现,外星母舰对地球的攻击竟然是随机的!必须尽快在地球上部署防御网络,抵御外星人母舰的攻击。
地球上的防御网络由节点和节点之间的能量连接组成,防御网络可以看成是一个 n 个点、 m 条边的简单无向图 G(V,E) ,每个防御节点对应 V 中的一个节点、每个能量连接对应 E 中的一条边。此外,在防御网络修建时考虑到能量传输效率,防御网络 G 每个节点至多只包含在一个简单环中
外星母舰的攻击是随机的,每次攻击开始后, JYY 都会本次攻击的情况选择一些防御节点 S\subseteq V ,并且用能量连接将这些防御节点连通,从而启动一个防御子网络。换言之, JYY 会选择 G 中边集的一个子集 H(S)\subseteq E ,它满足:

  1. (防御子网络连通) 如果我们建立新图 G'(V,H(S)) ,即用 H(S) 中的边连接 G 中的节点,则对于任意选择的防御节点 x,y\in S ,它们在 G' 中都连通。
  2. (防御子网络最小) 在满足条件 1 (防御子网络连通)的前提,选取的边数最小,即 \vert H(S)\vert 最小。

H(S) 是点集 S 在图 G 生成的斯坦纳树 (Steiner Tree) ,而 \vert H(S)\vert 则是启动防御子网络的最小代价。考虑到外星母舰随机攻击的方式, JYY 希望你计算启动防御子网络代价的期望:

\frac{1}{2^{\vert V\vert}}\sum_{S\subseteq V}\vert H(S)\vert

输入格式

输入第一行两个整数 n,m ,分别表示图中的节点数和边数。
接下来 m 行,每行两个整数 u,v(1\le u,v\le n) ,表示图中的一条边。输入保证没有自环和重边,并且满足每个节点至多包含在一个简单环中。

输出格式

输出一行,表示启动防御子网络的期望。
假设期望写成最简分式 P/Q 的形式, 则输出 P\cdot Q^{-1} \bmod 1,000,000,007 的余数,其中 Q^{-1} 为唯一的满足 Q\cdot Q^{-1} \equiv 1 \pmod{1,000,000,007} 的整数。

样例

样例输入 1

3 2
1 2
2 3

样例输出 1

750000006

样例输入 2

6 6
1 2
2 3
3 1
1 4
2 5
3 6

样例输出 2

468750006

样例解释

样例输入 1 是一条链,包含以下情况:

  • \{\}, \{1\}, \{2\}, \{3\},\vert H(S)\vert = 0 ;
  • \{1, 2\}, \{2, 3\}, \vert H(S)\vert = 1 ;
  • \{1, 3\}, \{1, 2, 3\}, \vert H(S)\vert = 2

因此 P/Q=3/4 P\cdot Q^{-1} = 750,000,006
样例输入 2 中 \sum_{S\subseteq V}\vert H(S)\vert = 174 ,因此 P/Q = 87/32 P\cdot Q^{-1} = 468,750,006 \bmod 1,000,000,007

数据范围与提示

对于 20\% 的数据,有 1\le n\le 8
对于 40\% 的数据,有 1\le n\le 20
对于 100\% 的数据,有 1\le n\le 200