#2088. [Poi2010]Teleportation

题目描述

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

输入格式

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

输出格式

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

样例

样例输入

10 10  

1 3  

3 5  

5 7  

7 9  

2 9  

1 4  

4 6  

6 8  

8 10  

2 10

样例输出

10  

 ![image](./1084/file/2088.jpg)   

实线连接的是已经造好传送门的两星球，虚线连接表示可以增加建造的传送门两星球。  

可以看出，建造了10对以后，从1号到2号星球还是Zy的250分钟最快。  

Notice:It's guaranteed that the data is valid.

数据范围与提示