P3505 [POI 2010] TEL-Teleportation

**译自 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$ 号点的最短路长度保持不变。 翻译来自于 [LibreOJ](https://loj.ac/p/2449)。

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