Build a Bridge

The monkeys at the zoo of Pordenone have $N$ trees (numbered from $0$ to $N-1$) to play on, with $M$ suspended bridges connecting some pairs of them. The bridges are numbered from $0$ to $M - 1$, and bridge $i$ connects trees $U_i$ and $V_i$ bidirectionally. There is at most one bridge between any pair of trees, and it is possible to get from tree $0$ to every other tree by crossing bridges.

The distance between two tress is the minimum number of bridges one has to cross to get from one tree to the other (without touching the ground).

Alessandro, the zookeeper, wants to add a new bridge to make the monkey area fancier. However, he is facing a problem: the monkey sitting on tree $0$ and the one sitting on tree $N - 1$ are sworn enemies, and if he were to make them fight he would be fired instantly. The monkeys would fight if, after installing the new bridge, the distance between tree $0$ and $N - 1$ was less than before. Also, Alessandro is not allowed to install a bridge between two trees that are already directly connected by a bridge.

Task

How many possible choices are there for the new bridge that would not get Alessandro fired?

Input data

The input consists of:

• a line containing integers $N$, $M$.
• $M$ lines, the $i$-th of which consisting of integers $U_{i}$, $V_{i}$.

Output data

The output must contain a single line consisting of a $64$-bit integer $C$, the number of ways to choose the location of the new bridge.

Constraints and clarifications

• $1 \le N \le 100 \ 000$
• $1 \le M \le 300 \ 000$
• $0 \le U_i \neq V_i < N$ for each $i=0\ldots M - 1$
• It is possible to reach any other tree from tree $0$ by crossing bridges.
• There is at most one bridge between any pair of trees.

Example 1

stdin

5 5
0 1
1 2
0 2
2 3
3 4

stdout

1

Explanation

In this sample case, there are $5$ trees and $5$ bridges. Initially, it is possible to reach tree $4$ from tree $0$ by crossing $3$ bridges: $0 — 2 — 3 — 4$.

• If Alessandro were to add a bridge between trees $0$ and $4$ it would be possible to reach tree $4$ by crossing $1$ bridge: $0 — 4$.
• If he were to add a bridge between trees $0$ and $3$ it would be possible to reach tree $4$ by crossing $2$ bridges: $0 — 3 — 4$.
• If he were to add a bridge between trees $1$ and $4$ it would be possible to reach tree $4$ by crossing $2$ bridges: $0 — 1 — 4$.
• If he were to add a bridge between trees $1$ and $3$ it would not be possible to reach tree $4$ by crossing fewer than $3$ bridges.
• If he were to add a bridge between trees $2$ and $4$ it would be possible to reach tree $4$ by crossing $2$ bridges: $0 — 2 — 4$.

The answer is therefore $1$, since the only bridge that Alessandro could build without getting fired is $1 — 3$.

Example 2

stdin

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

stdout

33