4456: 「POI2010」交通 Teleportation
内存限制：64 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
**译自 POI 2010 Stage 2. Day 2「[Teleportation](https://szkopul.edu.pl/problemset/problem/fKO3YZL0f_UM1nHQNDvw7mku/site/?key=statement)」**
现在有 $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$ 号点连通，且所有从 $1$ 到 $2$ 的路径长度均不少于 $250\min$ 。 Translated by vincent163