← 返回题目列表

AtCoder · dwango2015_finals_3

C. 驱动器

中文机器翻译题面 查看原题

問題文

二王后君住在 Nico Nico 镇。 有 N 个路口,每个路口有 它的编号为 1 到 N 。另外,2 连接两个交叉路口 M 有一条书路,每条路都有 它的编号为 1 到 M 。路 i 当你经过十字路口时 A_i 到交叉路口 B_i 或交叉点 B_i 到交叉路口 A_i 至 您可以在 2^i 时间内前往那里。

二王后君要去兜风了。行驶路线是一个交叉路口 从 1 开始,M 至少预订所有道路 1 我不止一次经过路口。 我想创建一条返回 1 的路线。求沿着这样的路线行驶所需的最短时间。然而,答案可能非常大,所以 除以1,000,000,007 求余数。


入力

输入将以以下形式从标准输入给出。

N M
A_1 B_1
A_2 B_2
:
A_M B_M
  • 1 行中,2 整数 N (2 ≦ N ≦ 400,000), M (1 ≦ M ≦ 500,000) 用空格分隔。这是Nico Nico镇的十字路口。 N 这条路是 M 表示这是一本书。 在
  • 2 从线 M 行中,给出了道路信息。其中 给出了 i 行中,2 整数 A_i, B_i (1 ≦ A_i ≦ N, 1 ≦ B_i ≦ N, A_i ≠ B_i) 。这就是路 i 是一个交集 A_i 和交叉路口 B_i 已连接。在同一交叉路口连接各组的道路是 2 仅此而已。而且保证您可以从任意一个路口走多条路到达任意一个路口。

部分点

针对此问题设置了部分分数。 满足

  • N ≦ 2,525 和 如果您对 M ≦ 2,525 的数据集 如果您正确回答 1 , 给出40 点。
  • 如果所有测试用例都回答正确,除了上述之外 70 点。

出力

最短驱动时间 除以 1,000,000,007 后的余数 1 行输出。在输出末尾插入换行符。


入力例1

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

出力例1

70

在此输入示例中,Niconico Town 具有以下结构。

例如,交叉路口 遵循 1,2,3,4,2,3,1 顺序所需的时间 2^1 + 2^3 + 2^2 + 2^5 + 2^3 + 2^4 = 70 。


入力例2

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

出力例2

2132