P6786: 建造军营（barrack）
传统题
1.000s
时间限制
512MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
A
国与 B 国正在激烈交战中，A
国打算在自己的国土上建造一些军营。
A
国的国土由 n 座城市组成，m
条双向道路连接这些城市，使得 任意两座城市均可通过道路直接或间接到达。A 国打算选择一座或多座城市（
至少一座），并在这些城市上各建造一座军营。
众所周知，军营之间的联络是十分重要的。然而此时 A 国接到情报，B
国将会于不久后袭击 A
国的一条道路，但具体的袭击目标却无从得知。如果 B
国袭击成功，这条道路将被切断，可能会造成 A
国某两个军营无法互相到达，这是 A
国极力避免的。因此 A 国决定派兵看守若干条道路（
可以是一条或多条，也可以一条也不看守），A
国有信心保证被派兵看守的道路能够抵御 B
国的袭击而不被切断。
A
国希望制定一个建造军营和看守道路的方案，使得 B
国袭击的无论是 A
国的哪条道路，都不会造成某两座军营无法互相到达。现在，请你帮 A
国计算一下可能的建造军营和看守道路的方案数共有多少。由于方案数可能会很多，你只需要输出其对 1, 000, 000, 007(10
^9 + 7)
取模的值即可。两个方案被认为是不同的，当且仅当存在至少一座城市在一个方案中建造了军营而在另一个方案中没有，或者存在至少一条道路在一个方案中被派兵看守而在另一个方案中没有。
【输入格式】
从文件 barrack.in
中读入数据。
第一行包含两个正整数 n, m
，分别表示城市的个数和双向道路的数量。
接下来 m
行，每行包含 2
个正整数 ui, vi
，描述一条连接 ui
和 vi
的双向道路。保证没有重边和自环。
【输出格式】
输出到文件 barrack.out
中。
输出一行包含一个整数，表示建造军营和看守道路的方案数对 1, 000, 000, 007(10
^9 +7)
取模的结果。
【样例 1
输入】
2 1
1 2
【样例 1
输出】
5
【样例 1
解释】
样例中，A
国共有 2
座城市，有 1
条道路连接它们。
所有可能的方案如下：
•
在城市 1
建军营，不看守这条道路；
•
在城市 1
建军营，看守这条道路；
•
在城市 2
建军营，不看守这条道路；
•
在城市 2
建军营，看守这条道路；
•
在城市 1, 2
建军营，看守这条道路；
【样例 2
输入】
4 4
1 2
2 3
3 1
1 4
【样例 2
输出】
184
【样例 3
】
见选手目录下的 barrack/barrack3.in
与 barrack/barrack3.ans
。
【样例 4
】
见选手目录下的 barrack/barrack4.in
与 barrack/barrack4.ans
。
【数据范围】
对于所有数据，保证 1 ≤ n ≤ 5 × 10
^5，n − 1 ≤ m ≤ 10
^6，1 ≤ ui, vi ≤ n，ui≠vi
。
测试点编号
|
n ≤
|
m ≤
|
特殊条件
|
1~3
|
8
|
10
|
无
|
4~7
|
16
|
25
|
8~9
|
3000
|
5000
|
10~11
|
5 × 10^5
|
10^6
|
特殊性质 A
|
12~14
|
m=n-1
|
15~16
|
m=n
|
17~20
|
无
|
特殊性质 A
：保证 m = n − 1
且第 i
条道路连接城市 i
与 i + 1。