Little town Nsk consists of n junctions connected by m bidirectional roads. Each road connects two distinct junctions and no two roads connect the same pair of junctions. It is possible to get from any junction to any other junction by these roads. The distance between two junctions is equal to the minimum possible number of roads on a path between them.

In order to improve the transportation system, the city council asks mayor to build one new road. The problem is that the mayor has just bought a wonderful new car and he really enjoys a ride from his home, located near junction s to work located near junction t. Thus, he wants to build a new road in such a way that the distance between these two junctions won't decrease. 

You are assigned a task to compute the number of pairs of junctions that are not connected by the road, such that if the new road between these two junctions is built the distance between s and t won't decrease.


-----Input-----

The firt line of the input contains integers n, m, s and t (2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000, 1 ≤ s, t ≤ n, s ≠ t) — the number of junctions and the number of roads in Nsk, as well as the indices of junctions where mayors home and work are located respectively. The i-th of the following m lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}), meaning that this road connects junctions u_{i} and v_{i} directly. It is guaranteed that there is a path between any two junctions and no two roads connect the same pair of junctions.


-----Output-----

Print one integer — the number of pairs of junctions not connected by a direct road, such that building a road between these two junctions won't decrease the distance between junctions s and t.


-----Examples-----
Input
5 4 1 5
1 2
2 3
3 4
4 5

Output
0

Input
5 4 3 5
1 2
2 3
3 4
4 5

Output
5

Input
5 6 1 5
1 2
1 3
1 4
4 5
3 5
2 5

Output
3

Difficulty: interview

Starter code:

Solutions:
import sys
import heapq

nnode,nedge,source,dest=list(map(int,sys.stdin.readline().split()))
source-=1;dest-=1
adjl=[[] for _ in range(nnode)]

for _ in range(nedge):
	u,v=list(map(int,sys.stdin.readline().split()))
	u-=1;v-=1
	adjl[u].append(v)
	adjl[v].append(u)

# why not BFS? >.<
def dijkstra_from(source):
	pq=[]
	dist=[10**9]*nnode

	dist[source]=0
	heapq.heappush(pq,(dist[source],source))
	while pq:
		dist_node,node=heapq.heappop(pq)
		if dist[node]!=dist_node: continue

		for adj in adjl[node]:
			if dist[adj]>dist_node+1:
				dist[adj]=dist_node+1
				heapq.heappush(pq,(dist[adj],adj))

	return dist

d_src=dijkstra_from(source)
d_dst=dijkstra_from(dest)

assert d_dst[source] == d_src[dest]

ans=0
for u in range(nnode):
	adj_to_u=[False]*u
	for v in adjl[u]:
		if v<u:
			adj_to_u[v]=True
	for v in range(u):
		if not adj_to_u[v]:
			if min(
			d_dst[u]+d_src[v]+1,
			d_src[u]+d_dst[v]+1
			)<d_src[dest]: continue
			ans+=1

print(ans)


R = lambda : map(int, input().split())
n,m,s,t = R()

graph = [set() for _ in range(n)]
edges = set()

for _ in range(m):
    u,v = R()
    graph[u-1].add(v-1)
    graph[v-1].add(u-1)
    edges.add((u-1,v-1))
    edges.add((v-1,u-1))

from collections import deque
def bfs(v):
    q = deque()
    q.append((v,0))
    dis = {}
    while q:
        vertex = q.popleft();
        dis[vertex[0]] = vertex[1]
        for nv in graph[vertex[0]]:
            if nv not in dis:
                dis[nv] = vertex[1]+1
                q.append((nv, vertex[1]+1))
    return dis

ds = bfs(s-1)
dt = bfs(t-1)
dist = bfs(s-1)[t-1]

res = (n*(n-1))//2-m
for i in range(n):
    for j in range(i+1, n):
        if (i,j) not in edges:
            if ds[i]+dt[j]+1 < dist:
                res -= 1
            elif ds[j]+dt[i]+1 <dist:
                res -= 1

print(res)

#!/usr/bin/env python3

import sys

[n, m, s1, t1] = list(map(int, sys.stdin.readline().strip().split()))
s, t = s1 - 1, t1 - 1
tos = [[] for _ in range(n)]
for _ in range(m):
	[u1, v1] = list(map(int, sys.stdin.readline().strip().split()))
	v, u = v1 - 1, u1 - 1
	tos[v].append(u)
	tos[u].append(v)

def S_l(v0, tos):
	n = len(tos)
	visited = [False for _ in range(n)]
	visited[v0] = True
	queue = [v0]
	hq = 0
	l = [0 for _ in range(n)]
	while len(queue) > hq:
		u = queue[hq]
		hq += 1
		for v in tos[u]:
			if not visited[v]:
				l[v] = l[u] + 1
				queue.append(v)
				visited[v] = True
	return l

lt = S_l(t, tos)
ls = S_l(s, tos)


d = lt[s]
count = 0
for u in range(n):
	for v in range(u):
		if (v not in tos[u]) and (min(lt[u] + ls[v], lt[v] + ls[u]) + 1 >= d):
			count += 1



print (count)


n, m, s, t = list(map(int , input().split()))
dors = []
for i in range(n+1):
    dors.append(set()) # инициализируем множество смежных вершин

for i in range(m):
    a, b = list(map(int , input().split()))
    dors[a].add(b)
    dors[b].add(a)

dists = [-1] *(n+1)   # расстояния от старта
dists[s] = 0
q = [s]
v = 0
while v < len(q):
    cur = q[v]
    for nextv  in dors[cur]:
        if dists[nextv] < 0:
            dists[nextv] = dists[cur] +1
            q.append(nextv)
    v += 1



distt = [-1] *(n+1) # расстояния от финиша
distt[t] = 0
q = [t]
v = 0
while v < len(q):
    cur = q[v]
    for nextv  in dors[cur]:
        if distt[nextv] < 0:
            distt[nextv] = distt[cur] +1
            q.append(nextv)
    v += 1



reqdist = dists[t] - dists [s] -1

res  =0

# print(dists)
# print(distt)

for v in range(1, n+1):
    for j in range(v+1, n+1):
        if  (j in dors[v]):
            continue
        if dists[v] + distt[j] >= reqdist and dists[j] + distt[v] >= reqdist:
            res +=1
            # print(v,j, 'can be added')


print(res)

# print(rset)


n,m,s,e = list(map(int,input().split()))
s -= 1
e -= 1
md = []
g = []
for i in range(n):
    md.append([-1,-1])
    g.append([])
for i in range(m):
    u,v = list(map(int,input().split()))
    g[u-1].append(v-1)
    g[v-1].append(u-1)

#bfs
md[s][0] = 0
d = 0
st = [s]
c = 1
#print('s')
while c < n:
    #print(c)
    d += 1
    st2 = []
    for node in st:
        for p in g[node]:
            if md[p][0] == -1:
                st2.append(p)
                md[p][0] = d

    c+=len(st2)
    st = st2[:]

#bfs
md[e][1] = 0
d = 0
st = [e]
c = 1
#print('s')
while c < n:
    #print(c)
    d += 1
    st2 = []
    for node in st:
        for p in g[node]:
            if md[p][1] == -1:
                st2.append(p)
                md[p][1] = d

    c+=len(st2)
    st = st2[:]
#print(md)
dis = md[e][0]
t = 0
for i in range(n):
    for j in range(i):
        if j in g[i]:continue
        if dis <= min(md[i][0] + md[j][1],md[j][0] + md[i][1])+1:
            t += 1
print(t)


n,m,s,t = list(map(int, input().split()))
G = [[] for _ in range(n+1)]
for i in range(m):
    a,b = list(map(int, input().split()))
    G[a].append(b)
    G[b].append(a)

dists = [n+1]*(n+1)
distt = [n+1]*(n+1)

# BFS find distance
T = [s]
count = 0
while T:
    newT = [] 
    for i in T:
        dists[i] = min(dists[i],count)
        for j in G[i]:
            if dists[j] == n+1:
                newT.append(j)
    count+=1
    T = newT

T = [t]
count = 0
while T:
    newT = [] 
    for i in T:
        distt[i] = min(distt[i],count)
        for j in G[i]:
            if distt[j] == n+1:
                newT.append(j)
    count+=1
    T = newT

count = 0
mm = dists[t]
for i in range(1,n+1):
    for j in range(i+1,n+1):
        if j in G[i]:
            continue
        if min(dists[i] + distt[j] + 1, dists[j] + distt[i] + 1) < mm:
            continue
        count += 1
print(count)


from queue import Queue


def BFS(v):
    used = {k: -1 for k in range(1, n + 1)}

    st = Queue()
    st.put(v)
    used[v] = 0

    while not st.empty():
        u = st.get()

        for v in range(1, n + 1):
            if graph[u][v] and used[v] == -1:
                used[v] = used[u] + 1
                st.put(v)

    return used


n, m, s, t = list(map(int, input().split()))

graph = {k: {k_: False for k_ in range(1, n + 1)} for k in range(1, n + 1)}

for i in range(m):
    a, b = list(map(int, input().split()))

    graph[a][b] = True
    graph[b][a] = True

S = BFS(s)
T = BFS(t)

ro = S[t]
ans = 0

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a != b and not graph[a][b] and S[a] + T[b] + 1 >= ro and S[b] + T[a] + 1 >= ro:
            ans += 1

print(ans // 2)


from array import array
n, m, s, t = list(map(int, input().split()))
neighbours = [array('H', [])]
neighbours.clear()
neighbours.append(0)
neighbours.extend((array('H', []) for _ in range(n)))
for __ in range(m):
	u, v = list(map(int, input().split()))
	neighbours[u].append(v)
	neighbours[v].append(u)
dist1 = array('H', [0]*(n+1))
visit = array('B', [0]+[1]*n)
queue = array('H', [s])
dists = array('H', [0])
index = 0
while index < len(queue):
	qi = queue[index]
	if visit[qi]:
		visit[qi] = 0
		di = dists[index]
		dist1[qi] = di
		for oth in neighbours[qi]:
			queue.append(oth)
			dists.append(di+1)
	index += 1
dist2 = array('h', [0]*(n+1))
visit = array('B', [0]+[1]*n)
queue = array('h', [t])
dists = array('h', [dist1[t]])
index = 0
while index < len(queue):
	qi = queue[index]
	if visit[qi]:
		visit[qi] = 0
		di = dists[index]
		dist2[qi] = di
		for oth in neighbours[qi]:
			queue.append(oth)
			dists.append(di-1)
	index += 1
res = 0
for s in range(1, n+1):
	for t in range(1, s):
		if (s not in neighbours[t]) and (dist1[s]+1 >= dist2[t]) and (dist1[t]+1 >= dist2[s]):
			res += 1
print(res)


from collections import *
inf = int(1e9)

n, m, s, t = map(int, input().split())
a = [set() for _ in range(n+1)]
for _ in range(m):
	u, w = map(int, input().split())
	a[u].add(w)
	a[w].add(u)
	
# d1
d1 = [inf] * (n + 1)
q = deque([s])
d1[s] = 0
while q:
	i = q.popleft()
	d = d1[i]
	for j in a[i]:
		if d1[j] == inf:
			q.append(j)
			d1[j] = d + 1
			
# d2
d2 = [inf] * (n + 1)
q = deque([t])
d2[t] = 0
while q:
	i = q.popleft()
	d = d2[i]
	for j in a[i]:
		if d2[j] == inf:
			q.append(j)
			d2[j] = d + 1			

# calc
ans = 0
v = d1[t]
for i in range(1, n+1):
	for j in range(i+1, n+1):
		if i not in a[j]:
			v1 = d1[i] + 1 + d2[j]
			v2 = d1[j] + 1 + d2[i]
			if v1 >= v and v2 >= v:
				ans += 1
print(ans)	

rd = lambda: list(map(int, input().split()))
n, m, s, t = rd()
a = [0] * (n + 1)
b = a + []
G = [[] for i in range(n + 1)]
for i in range(m):
    u, v = rd()
    G[u].append(v)
    G[v].append(u)
def bfs(x, a):
    q = [x]
    while q:
        c = q.pop()
        for y in G[c]:
            if not a[y]:
                a[y] = a[c] + 1
                q.insert(0, y)
    a[x] = 0
bfs(s, a)
bfs(t, b)
print(sum(min(a[i] + b[j], a[j] + b[i]) > a[t] - 2 for i in range(1, n + 1) for j in range(i + 1, n + 1)) - m)


def dj( s ,dist,g):
     dist[x] = 0
     q = [s]
     while q:
          c = q.pop()
          for to in g[c]:
               if not dist[to]:
                    dist[to] = dist[c]+1
                    q.insert(0,to)
     dist[s]=0
n,m,s,f= [ int(x) for x in input().split()]
s= s-1
f = f-1
g = [  [] for i in range(n)]
for i in range(m):
     x,y = [ int(x) for x in input().split()]
     x= x-1
     y =y -1
     g[x].append(y)
     g[y].append(x)
INF = int(1e9)
dist_s = [0 for i in range(n)]
dist_f = [0 for i in range(n)]
dj(s,dist_s,g)
dj(f,dist_f,g)
res = 0
for i in range(n):
     for j in range(i+1,n):
          if dist_s[i] +dist_f[j]+1 >= dist_s[f] and dist_f[i] + dist_s[j] +1 >=dist_s[f] and (j not in g[i]):
               res = res+1
print(res)




n,k,s,t=map(int,input().split())
m=[set() for i in range(n+1)]
for i in range(k):
    a,b=map(int,input().split())
    m[a].add(b)
    m[b].add(a)
forw=[-1]*(n+1)
back=forw.copy()
take,push=[],[s]
forw[s]=0
way=0
z=0
while push:
    way+=1
    take,push=push,take
    while take:
        a=take.pop()
        if a==t and not z:
            z=way-1
        for x in m[a]:
            if forw[x]==-1:
                forw[x]=way
                push.append(x)
take,push=[],[t]
back[t]=0
way=0
while push:
    way+=1
    take,push=push,take
    while take:
        a=take.pop()
        for x in m[a]:
            if back[x]==-1:
                back[x]=way
                push.append(x)
ans=0
for i in range(1,n):
    for j in range(i+1,n+1):
        if j not in m[i] and min(forw[j]+back[i],forw[i]+back[j])+1>=z:
            ans+=1
print(ans)

from collections import deque


def bfs(v):
    dist = [-1] * n
    used = [0] * n
    q = deque([])
    q.append(v)
    dist[v] = 0
    used[v] = 1
    while q:
        x = q.popleft()
        for i in range(len(graph[x])):
            if not used[graph[x][i]]:
                used[graph[x][i]] = 1
                dist[graph[x][i]] = dist[x] + 1
                q.append(graph[x][i])
    return dist
  
        
n, m, s, t = map(int, input().split())
s -= 1
t -= 1
graph = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
dt = bfs(t)
ds = bfs(s)
dist = ds[t]
ans = 0
for u in range(n - 1):
    for v in range(u + 1, n):
        if ds[u] + dt[v] + 1 >= dist and ds[v] + dt[u] + 1 >= dist:
            ans += 1
print(ans - m)

def bfs(s):
    d = [0] * n
    vs = {s}
    nr = {s}
    while len(vs) < n:
        cr = nr
        nr = set()
        for u in cr:
            for v in g[u] - vs:
                vs.add(v)
                d[v] = d[u] + 1
                nr.add(v)
    return d


n, m, s, t = list(map(int, input().split()))
s -= 1
t -= 1

g = [set() for _ in range(n)]
for i in range(m):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    g[u].add(v)
    g[v].add(u)

ds = bfs(s)
dt = bfs(t)
mindist = ds[t]

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if min(ds[i] + dt[j], ds[j] + dt[i]) >= mindist - 1:
            ans += 1

print(ans - m)


from collections import deque
def bfs(v):
    q = deque([])
    q.append(v)
    dist = [-1]*n
    visit = [0]*n
    q.append(v)
    dist[v] = 0
    visit[v] = 1
    while q:
        x = q.popleft()
        for i in range(len(graph[x])):
            if not visit[graph[x][i]]:
                visit[graph[x][i]] = 1
                dist[graph[x][i]] = dist[x]+1
                q.append(graph[x][i])
    return dist

n , m , s , t = map(int, input().split())
s-=1
t-=1
graph = [[] for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)
ds = bfs(s)
dt = bfs(t)
dist = ds[t]
ans = 0
for u in range(n):
    for v in range(u+1,n):
        if ds[u] + dt[v] +1  >= dist and ds[v] + dt[u] +1 >= dist:
            ans+=1
print(ans-m)

n, m, s, t = [int(x) for x in input().split()]
s -= 1
t -= 1
graph = []
for i in range(n):
    graph.append([])
for i in range(m):
    v, u = [int(x) - 1 for x in input().split()]
    graph[u].append(v)
    graph[v].append(u)
head = 0
q = [s]
used = [0] * n
ds = [0] * n
ds[s] = 0
used[s] = 1
while head != n:
    parent = q[head]
    head += 1
    for child in graph[parent]:
        if not used[child]:
            q.append(child)
            used[child] = 1
            ds[child] = ds[parent] + 1
head = 0
q = [t]
used = [0] * n
used[t] = 1
dt = [0] * n
dt[t] = 0
while head != n:
    parent = q[head]
    head += 1
    for child in graph[parent]:
        if not used[child]:
            q.append(child)
            used[child] = 1
            dt[child] = dt[parent] + 1
short = ds[t]
count = 0
for v in range(n):
    for u in range(v, n):
        if dt[u] + ds[v] + 1 >= short and ds[u] + dt[v] + 1 >= short and u != v and v not in graph[u]:
            count += 1
print(count)


def get_amount_variants(routes, n, s, t):
    """
    :param List[List[int]] routes:
    :param int n:
    :param int s:
    :param int t:
    :return: int
    """
    connects = [[] for _ in range(n + 1)]
    for st, end in routes:
        connects[st].append(end)
        connects[end].append(st)

    w_h = get_shortest_ways(connects, s)
    w_j = get_shortest_ways(connects, t)
    amount = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if min(w_h[i] + w_j[j], w_h[j] + w_j[i]) + 1 >= w_h[t] and i not in connects[j]:
                amount += 1
    return amount


def get_shortest_ways(connects, st):
    res = [int(1e9) if _ != st else 0 for _ in range(len(connects) + 1)]
    available = [(x, 0) for x in connects[st]]
    while len(available) > 0:
        point, weight = available.pop(0)
        if res[point] != 0 and res[point] < weight + 1:
            continue

        res[point] = weight + 1
        available += [(x, weight + 1) for x in connects[point] if res[x] == int(1e9) and x != st]
    return res


n, m, s, t = map(int, input().strip().split())
routes = []
for i in range(m):
    routes.append(map(int, input().split()))
print(get_amount_variants(routes, n, s, t))

# Project name: Fight Against Traffic

n,m,s,t = map(int, input().split())
a=[0]*(n+1)
b=list(a)
g= [[] for i in range(n+1)]

for i in range(m):
    u,v = map(int, input().split())
    g[u]+=[v]
    g[v]+=[u]

def bfs(x, a):
    q=[x]
    while q:
        c=q.pop()
        for y in g[c]:
            if not a[y]:
                a[y] = a[c]+1
                q.insert(0,y)
    a[x]=0

bfs(s,a)
bfs(t,b)

r=0
for i in range(1,n+1):
    for j in range(i + 1, n + 1):
        if not i in g[j] :
            if min(a[i]+b[j]+1, a[j]+b[i]+1) >= a[t]:
                r+=1
print (r)

from collections import deque

n,m,s,t = list(map(int,input().split(' ')))
n += 1
a = list()
for i in range(n):
  a.append(None)
for i in range(n):
    a[i] = list()
for i in range(m):
  u,v = list(map(int,input().split(' ')))
  a[u].append(v)
  a[v].append(u)

resS = [n]*n
resT = [n]*n

resS[s] = 0
resT[t] = 0

q = deque() #очередь

q.append(s)
while len(q)!=0:
  w = q.popleft()
  for i in a[w]:
    if resS[i] <= resS[w]:
        continue
    q.append(i)
    resS[i] = resS[w] + 1
     

q.append(t)
while len(q)!=0:
  w = q.popleft()
  for i in a[w]:
    if resT[i] <= resT[w]:
        continue
    q.append(i)
    resT[i] = resT[w] + 1

res = 0 
for i in range(1,n-1):
  for j in range(i+1,n):
    if not(j in a[i]) and resS[i]+resT[j]+1>=resS[t] and resT[i]+resS[j]+1>=resS[t]:
      res += 1

print(res)

from collections import deque
def bfs(s, level):
    level[s] = 0
    stack = deque([s])
    while stack:
        v = stack.popleft()
        for w in g[v]:
            if level[w] is -1:
                stack.append(w)
                level[w] = level[v] + 1
n, m, s, t = map(int, input().split())
g = []
for i in range(n):
    g.append(set())
for i in range(m):
    u, v = map(int, input().split())
    g[u - 1].add(v - 1)
    g[v - 1].add(u - 1)
a = [-1] * n
b = [-1] * n
bfs(s - 1, a)
bfs(t - 1, b)
cur = a[t - 1]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if (min(a[i] + b[j] + 1, a[j] + b[i] + 1) >= cur and (j not in g[i])):
            ans += 1
print(ans)

class Node:
    def __init__(self, label):
        self.label, self.ways, self.distances = label, set(), dict()

    def connect(self, other):
        self.ways.add(other)


class Graph:
    def __init__(self, count):
        self.nodes = [Node(i) for i in range(count)]

    def connect(self, a, b):
        node_a, node_b = self.nodes[a], self.nodes[b]
        node_a.connect(node_b)
        node_b.connect(node_a)

    def fill_distances(self, start):
        looked, queue, next_queue = {start}, {start}, set()
        start.distances[start] = 0
        while len(queue) + len(next_queue) > 0:
            for node in queue:
                for neighbour in node.ways:
                    if neighbour not in looked:
                        looked.add(neighbour)
                        next_queue.add(neighbour)
                        neighbour.distances[start] = node.distances[start] + 1
            queue, next_queue = next_queue, set()


def repeat(elem): 
    while True: 
        yield elem
def readline(types=repeat(int)):
    return [x[0](x[1]) for x in zip(types, input().split())]


def readinput():
    nodes, edges, start, finish = readline()
    start, finish = start - 1, finish - 1
    
    graph = Graph(nodes)
    for i in range(edges):
        a, b = readline()
        a, b = a - 1, b - 1
        graph.connect(a, b)

    return graph, graph.nodes[start], graph.nodes[finish]


def main():
    graph, start, finish = readinput()
    graph.fill_distances(start)
    graph.fill_distances(finish)

    distance = start.distances[finish]
    answer = 0
    for i in range(len(graph.nodes)):
        for j in range(i + 1, len(graph.nodes)):
            node_a, node_b = graph.nodes[i], graph.nodes[j]
            if node_a in node_b.ways: 
                continue
            if node_a.distances[start] + 1 + node_b.distances[finish] < distance:
                continue
            if node_a.distances[finish] + 1 + node_b.distances[start] < distance:
                continue
            answer += 1

    print(answer)


main()



class Node:
    def __init__(self, label):
        self.label, self.ways, self.distances = label, set(), dict()

    def connect(self, other):
        self.ways.add(other)


class Graph:
    def __init__(self, count):
        self.nodes = [Node(i) for i in range(count)]

    def connect(self, a, b):
        node_a, node_b = self.nodes[a], self.nodes[b]
        node_a.connect(node_b)
        node_b.connect(node_a)

    def fill_distances(self, start):
        looked, queue, next_queue = {start}, {start}, set()
        start.distances[start] = 0
        while len(queue) + len(next_queue) > 0:
            for node in queue:
                for neighbour in node.ways:
                    if neighbour not in looked:
                        looked.add(neighbour)
                        next_queue.add(neighbour)
                        neighbour.distances[start] = node.distances[start] + 1
            queue, next_queue = next_queue, set()


def repeat(elem): 
    while True: 
        yield elem
def readline(types=repeat(int)):
    return map(lambda x: x[0](x[1]), zip(types, input().split()))


def readinput():
    nodes, edges, start, finish = readline()
    start, finish = start - 1, finish - 1
    
    graph = Graph(nodes)
    for i in range(edges):
        a, b = readline()
        a, b = a - 1, b - 1
        graph.connect(a, b)

    return graph, graph.nodes[start], graph.nodes[finish]


def main():
    graph, start, finish = readinput()
    graph.fill_distances(start)
    graph.fill_distances(finish)

    distance = start.distances[finish]
    answer = 0
    for i in range(len(graph.nodes)):
        for j in range(i + 1, len(graph.nodes)):
            node_a, node_b = graph.nodes[i], graph.nodes[j]
            if node_a in node_b.ways: 
                continue
            if node_a.distances[start] + 1 + node_b.distances[finish] < distance:
                continue
            if node_a.distances[finish] + 1 + node_b.distances[start] < distance:
                continue
            answer += 1

    print(answer)


main()

def bfs(beg,deeps,d):
    levels=[beg]
    while levels:
        cur=levels.pop()
        for x in d[cur]:
            if deeps[x]==0:
                deeps[x]=deeps[cur]+1
                levels.insert(0,x)
    deeps[beg]=0
    return

n,m,s,t=list(map(int,input().split()))

d=[[] for i in range(n+1)]

for i in range(m):
    x,y=list(map(int,input().split()))
    d[x].append(y)
    d[y].append(x)

froms=[0 for i in range(n+1)]
fromt=[0 for i in range(n+1)]

bfs(s,froms,d)
bfs(t,fromt,d)

ans=0
for i in range(1,n+1):
    for j in range(i+1,n+1):
        ij=min(froms[i]+fromt[j]+1,froms[j]+fromt[i]+1)
        if ij>=froms[t]: ans+=1
print(ans-m)


import sys
import heapq
class Node(object):
    def __init__(self,name):
        self.name=name
        self.minDistance=sys.maxsize
        self.paths=[]
        self.baap=None
    def __lt__(self,other):
        return(self.minDistance<other.minDistance)
class Path(object):
    def __init__(self,start,end,weight):
        self.start=start
        self.end=end
        self.weight=weight
class Dijkstra(object):
    def __init__(self,nodelist,start):
        self.nodelist=nodelist
        self.start=start
    def calculateShortestPath(self):
        queue=[]
        self.nodelist[int(self.start)-1].minDistance=0
        heapq.heappush(queue,nodelist[int(self.start)-1])
        while len(queue)>0:
            actualNode=heapq.heappop(queue)
            for i in actualNode.paths:
                u=self.nodelist[int(i.start)-1]
                v=self.nodelist[int(i.end)-1]
                newdis=u.minDistance+i.weight
                if newdis<v.minDistance:
                    v.minDistance=newdis
                    v.baap=u
                    heapq.heappush(queue,v)
    def disp(self):
        arr=[]
        for i in self.nodelist:
          arr.append(i.minDistance)
        return arr
#Dj till here
    

n,m,s,t=list(map(int,input().split(' ')))
n,m=int(n),int(m)
nodelist=[]
for i in range(1,n+1):
    nodelist.append(Node(str(i)))
pathdd=[]
for i in range(n):
  temp=[]
  for j in range(n):
    temp.append(-1)
  pathdd.append(temp)
for i in range(m):
    st,en=input().split(' ')
    pathdd[int(st)-1][int(en)-1]=1;pathdd[int(en)-1][int(st)-1]=1;
    nodelist[int(st)-1].paths.append(Path(st,en,1))
    nodelist[int(en)-1].paths.append(Path(en,st,1))
dij=Dijkstra(nodelist,s)
dij.calculateShortestPath()
dn1=dij.disp()#minimum Distance of all nodes from source node
mindis=dn1[t-1]
for i in nodelist:
  i.minDistance=sys.maxsize#Reinitializing all distance to infinity
dij=Dijkstra(nodelist,t)
dij.calculateShortestPath()
dn2=dij.disp()#minimum distance of all nodes from target node
#print(dn1,"\n",dn2);
ctr=0
for u in range(len(nodelist)-1):
  for v in range(u+1,len(nodelist)):
    if dn1[u]+1+dn2[v]>=mindis and dn1[v]+dn2[u]+1>=mindis and pathdd[u][v]==-1:
      ctr+=1;
print(ctr)


from collections import deque, namedtuple
from heapq import *
from sys import stdin

inf = float('inf')
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
    return Edge(start, end, cost)


class Graph:
    def __init__(self, edges, bi=True):
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))
        self.edges = [make_edge(*edge) for edge in edges]
        self.vertices = set(
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            ))
        self.neighbors = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            self.neighbors[edge.start].add(edge.end)

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if[edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'
        distances = {vertex: inf for vertex in self.vertices}
        distances[source] = 0

        q, seen = [(0, source)], set()
        while q:
            (curr_cost, current_vertex) = heappop(q)
            if current_vertex in seen:
                continue
            seen.add(current_vertex)
            for neighbor in self.neighbors[current_vertex]:
                cost = 1
                if neighbor in seen:
                    continue
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbor]:
                    distances[neighbor] = alternative_route
                    heappush(q, (alternative_route, neighbor))

        return distances


n, m, s, t = [int(x) for x in stdin.readline().rstrip().split()]

verts = []
for i in range(m):
    verts.append(tuple([int(x) for x in stdin.readline().rstrip().split()]))
rev_verts = []
for i in verts:
    rev_verts.append((i[1], i[0]))
for i in rev_verts:
    verts.append(i)
graph = Graph(verts)
s_dist = graph.dijkstra(s, t)
t_dist = graph.dijkstra(t, s)
SHORTEST_DIST = s_dist[t]
count = 0

for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if j not in graph.neighbors[i] and \
                i not in graph.neighbors[j] and \
                s_dist[i] + t_dist[j] + 1 >= SHORTEST_DIST and \
                s_dist[j] + t_dist[i] + 1 >= SHORTEST_DIST:
            count = count + 1

print(count)