题目描述

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

现在有 $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$ 号点的最短路长度保持不变。

样例

input

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

output

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