时间限制: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
说明
在2号城市和7号城市间修建新的高速公路之后,只有连接1号城市和3号城市的高速公路被破坏才可以导致王国不能继续正常运转,概率为
。