#2449. 「POI2010」交通 Teleportation

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

现在有 n 个点,目前在 1 号点和 2 号点之间有一条无向边,长度为 250\min
除此之外,还有 m 条无向边,长度都为 1\ \textrm{h} (即 60\min ), Byteasar 想知道,还能最多在添加多少条长度为 1\ \textrm{h} 的无向边,使得新图无重边无自环,且 1 号点到 2 号点的最短路仍为 250\min

输入格式

第一行两个空格隔开的正整数 n,m
接下来 m 行,每行两个空格隔开的正整数 u_i,v_i ,描述原有的边。

输出格式

一行一个整数,表示最多添加多少条边,可以使 1 号点到 2 号点的最短路长度保持不变。

样例

样例输入

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

样例输出

10

数据范围与提示

对于 100\% 的数据, 2\le n\le 40\ 000,0\le m\le 1\ 000\ 000,1\le u_i,v_i\le n ,保证只考虑已有的边时, 1 号点与 2 号点联通,且最短路长度大于 250\min

Translated by vincent163