#D0069. 建造军营

建造军营

题目描述

A 国与 B 国正在激烈交战中,A 国打算在自己的国土上建造一些军营。

A 国的国土由 nn 座城市组成,mm 条双向道路连接这些城市,使得任意两座城市均可通过道路直接或间接到达。A 国打算选择一座或多座城市(至少一座),并在这些城市上各建造一座军营。

众所周知,军营之间的联络是十分重要的。然而此时 A 国接到情报,B 国将会于不久后袭击 A 国的一条道路,但具体的袭击目标却无从得知。如果 B 国袭击成功,这条道路将被切断,可能会造成 A 国某两个军营无法互相到达,这是 A 国极力避免的。因此 A 国决定派兵看守若干条道路(可以是一条或多条,也可以一条也不看守),A 国有信心保证被派兵看守的道路能够抵御 B 国的袭击而不被切断。

A 国希望制定一个建造军营和看守道路的方案,使得 B 国袭击的无论是 A 国的哪条道路,都不会造成某两座军营无法互相到达。现在,请你帮 A 国计算一下可能的建造军营和看守道路的方案数共有多少。由于方案数可能会很多,你只需要输出其对 1,000,000,007(109+7)1,000,000,007\left(10^{9}+7\right) 取模的值即可。两个方案被认为是不同的,当且仅当存在至少一 座城市在一个方案中建造了军营而在另一个方案中没有,或者存在至少一条道路在一个 方案中被派兵看守而在另一个方案中没有。

输入格式

第一行包含两个正整数 n,mn,m,分别表示城市的个数和双向道路的数量。

接下来 mm 行,每行包含两个正整数 ui,viu_{i},v_{i},描述一条连接 uiu_{i}viv_{i} 的双向道路。保证没有重边和自环。

输出格式

输出一行包含一个整数,表示建造军营和看守道路的方案数对 1,000,000,007(109+7)1,000,000,007\left(10^{9}+ 7\right) 取模的结果。

样例 #1

样例输入 #1

2 1
1 2

样例输出 #1

5

样例 #2

样例输入 #2

4 4
1 2
2 3
3 1
1 4

样例输出 #2

184

样例 #3

样例输入 #3

见附加文件里的 barrack/barrack3.in

样例输出 #3

见附加文件里的 barrack/barrack3.ans

样例 #4

样例输入 #4

见附加文件里的 barrack/barrack4.in

样例输出 #4

见附加文件里的 barrack/barrack4.ans

提示

样例 1 解释

A 国有两座城市,一条道路连接他们。所有可能的方案如下:

  • 在城市 11 建军营, 不看守这条道路;
  • 在城市 11 建军营, 看守这条道路;
  • 在城市 22 建军营, 不看守这条道路;
  • 在城市 22 建军营, 看守这条道路;
  • 在城市 1,21,2 建军营, 看守这条道路。

数据规模与约定

对所有数据,保证 1n5×1051 \leq n \leq 5 \times 10^5n1m106n - 1 \leq m \leq 10^61ui,vin1 \leq u_i, v_i \leq nuiviu_i \neq v_i

各测试点的信息如下

测试点编号 nn \leq mm \leq 特殊条件
131 \sim 3 88 1010
474 \sim 7 1616 2525
898 \sim 9 30003000 50005000
101110 \sim 11 5×1055 \times 10^5 10610^6 特殊性质 A\mathrm{A}
121412 \sim 14 m=n1m = n - 1
151615 \sim 16 m=nm = n
172017 \sim 20

特殊性质 A\mathrm{A}:保证 m=n1m=n-1 且第 ii 条道路连接城市 iii+1i+1

大样例:barrack.zip