题目描述

译自 POI 2010 Stage 2. Day 2「Teleportation」

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

输入格式

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

输出格式

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

翻译来自于 LibreOJ。

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

10

提示

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