Minus One

Time limit2sMemory limit512 MB

Summary

Count the non-edges whose addition shortens the shortest s-t path by exactly one, given an undirected graph with up to 100,000 vertices.

Level: Medium7 of 10
Topics: Graph, BFS, Shortest path, Combinatorics
Solved: No attempts yet

Problem

Ikuta is unusually attached to undirected graphs. Among pairs $(G,s,t)$ consisting of an undirected graph $G$ and two of its vertices $s,t$ , he likes the ones with large "beauty". The "beauty" of a pair $(G,s,t)$ is the number of edges $e = \{u, v\}$ ( $u$ and $v$ are two distinct vertices of $G$ ) such that the length of the shortest path from $s$ to $t$ in $G$ is exactly 1 greater than the length of the shortest path from $s$ to $t$ in the undirected graph obtained by adding $e$ to $G$ .

Your job is to write a program that computes this "beauty" for a given pair $(G,s,t)$ .

Input

The input is given in the following format.

$N$ $M$ $s$ $t$

$x_1$ $y_1$

...

$x_i$ $y_i$

...

$x_M$ $y_M$

First, the integers $N,M,s,t$ , which denote the number of vertices of the undirected graph, the number of edges, and two vertices, are given. Lines 2 through $M+1$ each give two vertices connected by an edge. (The vertex set of $G$ is $\{1,..., N\}$ .)

Output

Let the given graph be $G$ . Print the "beauty" of the pair $(G,s,t)$ on one line.

Constraints

Each variable in the input satisfies the following constraints.

$2\leq N \leq 100,000$
$1\leq M \leq 300,000$
$1\leq s,t,x_i,y_i \leq N$
$s$ and $t$ are different
It is guaranteed that $t$ is reachable from $s$

Examples4

Example 1
Input
```
3 2 1 3
1 2
2 3
```
Expected output
```
1
```

Example 2

Input

Expected output

Example 3
Input
```
4 3 1 4
1 2
3 4
4 1
```
Expected output
```
0
```
Example 4
Input
```
9 7 8 9
9 6
6 5
3 6
3 7
2 5
8 5
1 4
```
Expected output
```
2
```