小雀和他的王国
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

年纪轻轻的小雀当上了国王。
小雀的王国中一共有n座城市(编号为1~n),被m条双向的高速公路连接,任意两个城市之间都可以通过若干条高速公路互相到达。
但是在小雀的王国里,经常发生自然灾害。一次突发的自然灾害会随机破坏一条高速公路,并且有可能使得某两个城市之间无法到达彼此,这样整个王国就不能继续正常运转了。小雀为此很是苦恼。
于是小雀决定再修建一条高速公路,连接某两个城市,使得下一次突发自然灾害的时候,整个王国不能继续正常运转的概率最小。但是他不知道该如何选择新高速公路所连接的两个城市。
请你帮助他选择新建高速的方案,并求出新的高速公路建成之后,突发自然灾害时,整个王国不能继续正常运转的最小概率。答案对109+7取模。
对于100%的数据,2≤ n,m 200000;

输入描述:

第一行包含两个整数n,m,表示城市的数量和现有的高速公路的数量。
接下来m行,每行包含两个整数ui,vi,表示一条高速公路所连接的两个城市的编号。

输出描述:

一行一个整数,表示最小概率。
若最小概率可以表示为,请输出
示例1

输入

复制
7 7
1 2
1 3
1 6
2 4
2 5
4 5
6 7

输出

复制
125000001

说明

在2号城市和7号城市间修建新的高速公路之后,只有连接1号城市和3号城市的高速公路被破坏才可以导致王国不能继续正常运转,概率为\frac{1}{8}