UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2088. [Poi2010]Teleportation

统计 下载数据

Description

Zy大帝拥有n个星球,因为距离非常遥远,所以Zy在他所居住的1号星球和他的军事基地霸中所在的2号星球建造了两个传送门,这样从1号星球到2号星球就只需要250分钟,回去也一样(双向)。由于科技的发展,各个星球陆陆续续建造了和自己居民最经常去的星球之间的传送门,并且他们的传送门只需要1个小时(真快啊!),他们发现和别的星球建设传送门对促进经济发展有很大的帮助,于是向和其他所有星球建设传送门发展,Zy突然发现两两星球的传送门的建设会威胁到他的安全,可是他又想促进自己帝国的发展,于是他请到了他精心培养的你,希望你能帮他解决这个难题。

Input

输入:第一行为两个由空格隔开的整数n(2<=n<=40000)和m(0<=m<=1000000),n表示星球数,m表示其他星球已经建造的传送门的对数(传送门都是两两建造的)(不包括Zy在1号和2号的)。接下来m行每行两个由空格隔开的整数想x,y(2<=x,y<=40000),表示这两个星球建造了传送门连接。

Output

输出:还能让多少对传送门建造,但又不会比Zy从1号星球到2号星球快(就是说增加传送门后,从1号星球到2号星球还是Zy的传送门最快)。

Sample Input

10 10
1 3
3 5
5 7
7 9
2 9
1 4
4 6
6 8
8 10
2 10

Sample Output

10

实线连接的是已经造好传送门的两星球,虚线连接表示可以增加建造的传送门两星球。
可以看出,建造了10对以后,从1号到2号星球还是Zy的250分钟最快。
Notice:It's guaranteed that the data is valid.

Hint

Source