Problem: Ikta has an extraordinary feeling for undirected graphs. Ikta likes the undirected graph G and its two-point s, t pair (G, s, t) that has the greatest "beauty". The "beauty" of a pair (G, s, t) is the edge e = \\ {u, v \\} (u and v are two different points of G), and the shortest path from s to t in G. Is the number of things whose length is greater than the length of the shortest path from s to t in the undirected graph with g plus e.

Your job is to write a program that seeks its "beauty" given a pair (G, s, t).



Input

The input is given in the following format.

> N M s t
> x1 y1
> ...
> xi yi
> ...
> xM yM
>

First, the number of vertices, the number of edges, and the integers N, M, s, t representing the two vertices of the undirected graph are input. From the 2nd line to the M + 1th line, two vertices connected by edges are input. (However, let the set of G vertices be \\ {1, ..., N \\}.)

Constraints

Each variable being input satisfies the following constraints.

* 2 ≤ N ≤ 100,000
* 1 ≤ M ≤ 300,000
* 1 ≤ s, t, xi, yi ≤ N
* Different from s and t
* Guaranteed to reach t from s

Output

When the given graph is G, output the "beauty" of the set (G, s, t) in one line.

Examples

Input

3 2 1 3
1 2
2 3


Output

1


Input

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


Output

7


Input

4 3 1 4
1 2
3 4
4 1


Output

0


Input

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


Output

2

Solution (in PYTHON3):

Solution:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    while 1:
        n = I()
        if n == 0:
            quit()
        a = LI()
        m = sum(a)/n
        c = 0
        for i in range(n):
            if a[i] <= m:
                c += 1
        print(c)
    return

#B
def B():
    while 1:
        n = I()
        if n == 0:
            quit()
        t = [0 for i in range(24*3600)]
        for i in range(n):
            x,y = input().split()
            x = list(map(int, x.split(":")))
            y = list(map(int, y.split(":")))
            l = x[0]*3600+x[1]*60+x[2]
            r = y[0]*3600+y[1]*60+y[2]
            t[l] += 1
            t[r] -= 1
        ans = 0
        for i in range(24*3600-1):
            t[i+1] += t[i]
            ans = max(ans, t[i])
        print(ans)
    return
#C
def C():
    n = I()
    if n == 0:
        print(1)
    elif n == 1:
        print(2)
    elif n == 2:
        print(1)
    else:
        print(0)
    return

#D
def D():
    def dijkstra(s):
        d = [float("inf") for i in range(n)]
        q = [[0,s]]
        d[s] = 0
        while q:
            dx,x = heappop(q)
            for y in v[x]:
                if dx+1 < d[y]:
                    d[y] = d[x]+1
                    heappush(q,[d[y],y])
        return d
    n,m,s,t = LI()
    s -= 1
    t -= 1
    v = [[] for i in range(n)]
    for i in range(m):
        x,y = LI()
        x -= 1
        y -= 1
        v[x].append(y)
        v[y].append(x)
    l = dijkstra(s)
    l2 = dijkstra(t)
    k = l[t]-2
    d = defaultdict(int)
    ans = 0
    for i in l2:
        d[i] += 1
    for i in l:
        ans += d[max(-1,k-i)]
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    D()