King Sejong

Sejong is the king of a solar system with $n$ planets. There are so many planets that he long ago gave up on naming them; instead each planet is identified by a number from $1$ to $n$. Sejong's home is on planet $1$, and his favorite internet cafe is on planet $2$.

To reach the cafe faster than anyone else and never miss a happy-hour event, Sejong keeps a private secret teleporter that directly connects planet $1$ and planet $2$. This secret teleporter is bidirectional and takes $250$ minutes for one trip.

Meanwhile, many public transit teleporters have been installed between the planets. Each transit teleporter is also bidirectional and takes exactly $1$ hour ($60$ minutes) per trip. To boost the economy, the citizens have asked Sejong to install even more transit teleporters.

Sejong wants to grant as many requests as possible, but he insists on one rule: using only transit teleporters, the shortest travel time between planet $1$ and planet $2$ must always stay strictly greater than $250$ minutes, so that his secret teleporter always remains the fastest route. Since one transit trip takes $60$ minutes, this means every path between the two planets must always use at least $5$ transit teleporters.

Find the maximum number of additional transit teleporters that can be installed while keeping this rule. Installing a second teleporter between a pair of planets that are already directly connected is pointless, so it is never done: at most one teleporter joins any pair of distinct planets, and no teleporter connects a planet to itself.

The first line contains the number of planets $n$ and the number of already installed transit teleporters $m$, separated by a space. ($2 \le n \le 40000$, $0 \le m \le 1000000$)

Each of the next $m$ lines contains two distinct planet numbers $u$ and $v$ joined by a transit teleporter. ($1 \le u, v \le n$, $u \ne v$) Sejong's secret teleporter is not included here. No pair of planets is listed more than once.

It is guaranteed that, using only the already installed transit teleporters, there is no route between planet $1$ and planet $2$ shorter than $250$ minutes along any path. (Longer routes may still exist.)

Print, on one line, the maximum number of additional transit teleporters that can be installed while keeping the rule.

The figure above shows one example configuration. Solid lines are transit teleporters that are already installed, and dashed lines are transit teleporters that may still be added without breaking the rule.