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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Shortest paths


Solutions:
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()


import sys

def dijkstra_t(adj: list, start: int, inf: int=10 ** 18) -> list:
	from heapq import heappush, heappop
	v_count = len(adj)
	dists = [inf] * v_count
	dists[start] = 0
	(hq, rem) = ([(0, start)], v_count - 1)
	while hq and rem:
		(cost, src) = heappop(hq)
		if dists[src] < cost:
			continue
		rem -= 1
		for (dest, _cost) in adj[src]:
			newcost = cost + _cost
			if dists[dest] > newcost:
				dists[dest] = newcost
				heappush(hq, (newcost, dest))
	return dists
(n, m, s, t) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
s -= 1
t -= 1
adj = [[] for _ in range(n)]
matrix = [[0] * n for _ in range(n)]
for (u, v) in (map(int, line.decode('utf-8').split()) for line in sys.stdin.buffer):
	adj[u - 1].append((v - 1, 1))
	adj[v - 1].append((u - 1, 1))
	matrix[u - 1][v - 1] = matrix[v - 1][u - 1] = 1
dist1 = dijkstra_t(adj, s, 10 ** 9)
dist2 = dijkstra_t(adj, t, 10 ** 9)
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		if matrix[i][j]:
			continue
		if dist1[i] + 1 + dist2[j] >= dist1[t] and dist1[j] + 1 + dist2[i] >= dist1[t]:
			ans += 1
print(ans)


(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)
md[s][0] = 0
d = 0
st = [s]
c = 1
while c < n:
	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[:]
md[e][1] = 0
d = 0
st = [e]
c = 1
while c < n:
	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[:]
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)


from collections import *
inf = int(1000000000.0)
(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 = [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 = [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
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)


(n, m, s, t) = map(int, input().split())
dic = {}
hasEdge = []
for i in range(n):
	dic[i] = []
for i in range(n):
	hasEdge.append([])
	for j in range(n):
		hasEdge[-1].append(0)
for i in range(m):
	(a, b) = map(int, input().split())
	dic[a - 1].append(b - 1)
	dic[b - 1].append(a - 1)
	hasEdge[a - 1][b - 1] = 1
	hasEdge[b - 1][a - 1] = 1
distS = {}
distD = {}

def shortestDist(source, n):
	lis = []
	sol = {}

	def bfs(source):
		global dic
		nonlocal lis
		nonlocal sol
		lis.append(source)
		sol[source] = 0
		while len(lis) != 0:
			temp = lis.pop(0)
			for i in dic[temp]:
				if sol.get(i) == None:
					sol[i] = sol[temp] + 1
					lis.append(i)
	bfs(source)
	for i in range(n):
		if sol.get(i) == None:
			sol[i] = float('Inf')
	return sol
distS = shortestDist(s - 1, n)
distD = shortestDist(t - 1, n)
count = 0
for i in range(n):
	for j in range(i + 1, n):
		if hasEdge[i][j] == 0 and min(distS[i] + 1 + distD[j], distS[j] + 1 + distD[i]) >= distS[t - 1]:
			count += 1
print(count)


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

def bfs(x, d):
	q = [x]
	while q:
		c = q.pop(0)
		for y in G[c]:
			if not d[y]:
				d[y] = d[c] + 1
				q.append(y)
	d[x] = 0
ds = [0 for i in range(n + 1)]
dt = [0 for i in range(n + 1)]
bfs(s, ds)
bfs(t, dt)
D = ds[t]
pairs = 0
for u in range(1, n + 1):
	for v in range(u + 1, n + 1):
		if u in G[v]:
			continue
		min_long = min(ds[u] + dt[v] + 1, ds[v] + dt[u] + 1)
		if min_long >= D:
			pairs += 1
print(pairs)


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)


(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)


rd = lambda : 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)


import heapq
import sys
input = sys.stdin.readline

def dijkstra(start: int, graph: list) -> list:
	INF = 10 ** 18
	n = len(graph)
	dist = [INF] * n
	dist[start] = 0
	q = [(0, start)]
	cost = 1
	while q:
		(d, v) = heapq.heappop(q)
		if dist[v] < d:
			continue
		for nxt_v in graph[v]:
			if dist[v] + cost < dist[nxt_v]:
				dist[nxt_v] = dist[v] + cost
				heapq.heappush(q, (dist[nxt_v], nxt_v))
	return dist
(n, m, s, t) = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]
s -= 1
t -= 1
graph = [[] for i in range(n)]
for (a, b) in edges:
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
dist_s = dijkstra(s, graph)
dist_t = dijkstra(t, graph)
st = dist_s[t]
ans = 0
for u in range(n):
	for v in range(u + 1, n):
		d = min(dist_s[u] + 1 + dist_t[v], dist_s[v] + 1 + dist_t[u])
		if st <= d:
			ans += 1
ans -= m
print(ans)


from collections import deque
(n, m, s, t) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)

def bfs(p, d):
	d[p] = 0
	q = deque([p], n)
	while q:
		x = q.popleft()
		for j in g[x]:
			if d[j] == -1:
				d[j] = d[x] + 1
				q.append(j)
d1 = [-1] * n
d2 = [-1] * n
bfs(s - 1, d1)
bfs(t - 1, d2)
z = d2[s - 1]
o = 0
for i in range(n):
	for j in range(i + 1, n):
		if j not in g[i] and d1[i] + d2[j] + 1 >= z and (d1[j] + d2[i] + 1 >= z):
			o += 1
print(o)


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) = map(int, input().split())
d = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = 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)


(n, m, s, t) = map(int, input().split())
from collections import defaultdict
d = defaultdict(list)
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	d[a].append(b)
	d[b].append(a)

def calc(d, s, t):
	dist = [10 ** 9] * n
	vis = [0] * n
	q = [s]
	dist[s] = 0
	vis[s] = 1
	while q:
		t = q.pop(0)
		for i in d[t]:
			if not vis[i]:
				dist[i] = dist[t] + 1
				vis[i] = 1
				q.append(i)
	return dist
s -= 1
t -= 1
dist_s = calc(d, s, t)
dist_t = calc(d, t, t)
ans = 0
mini = dist_s[t]
(s, t) = (min(s, t), max(s, t))
for i in range(n):
	for j in range(i + 1, n):
		if i not in d[j] and (not (i == s and j == t)):
			psbl1 = dist_s[i] + 1 + dist_t[j]
			psbl2 = dist_t[i] + 1 + dist_s[j]
			m = min(psbl1, psbl2)
			if m >= mini:
				ans += 1
print(ans)


(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
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(res)


def get_amount_variants(routes, n, s, t):
	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(1000000000.0) 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(1000000000.0) 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))


(n, m, s, t) = map(int, input().split())
G = [[] for _ in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	G[a].append(b)
	G[b].append(a)
dists = [n + 1] * (n + 1)
distt = [n + 1] * (n + 1)
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)


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
(n, m, s, t) = 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()
mindis = dn1[t - 1]
for i in nodelist:
	i.minDistance = sys.maxsize
dij = Dijkstra(nodelist, t)
dij.calculateShortestPath()
dn2 = dij.disp()
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 defaultdict
(nodes, edges, start, end) = map(int, input().split())
shortest = [-1] * (nodes + 1)
shortest[start] = 0
dic = defaultdict(set)
for i in range(edges):
	(x, y) = map(int, input().split())
	dic[x].add(y)
	dic[y].add(x)
queue = [start]

def bfs(queue):
	j = 0
	while j < len(queue):
		node = queue[j]
		for i in dic[node]:
			if shortest[i] == -1:
				shortest[i] = shortest[node] + 1
				queue.append(i)
		j += 1
bfs(queue)
shorteststart = shortest[:]
shortest = [-1] * (nodes + 1)
shortest[end] = 0
queue = [end]
bfs(queue)
shortestend = shortest[:]
output = 0
mindistance = shorteststart[end]
for i in range(1, nodes + 1):
	for j in range(i + 1, nodes + 1):
		if j not in dic[i]:
			if min(shorteststart[i] + shortestend[j], shortestend[i] + shorteststart[j]) + 1 >= mindistance:
				output += 1
print(output)


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) = map(int, input().split())
s -= 1
t -= 1
g = [set() for _ in range(n)]
for i in range(m):
	(u, v) = 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)


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(1000000000.0)
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)


from queue import Queue
(n, m, s, t) = map(int, input().split())
s -= 1
t -= 1
g = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1][v - 1] = 1
	g[v - 1][u - 1] = 1

def bfs(g, s):
	distance = [float('inf')] * len(g)
	distance[s] = 0
	q = Queue()
	q.put(s)
	while not q.empty():
		node = q.get()
		for (i, el) in enumerate(g[node]):
			if el > 0 and distance[i] == float('inf'):
				distance[i] = distance[node] + 1
				q.put(i)
	return distance
d_s = bfs(g, s)
d_t = bfs(g, t)
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		if not j == i and (not g[i][j] == 1) and (d_s[i] + d_t[j] + 1 >= d_s[t]) and (d_t[i] + d_s[j] + 1 >= d_s[t]):
			ans += 1
print(ans)


from array import array
(n, m, s, t) = 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) = 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)


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) = map(int, input().split())
s -= 1
t -= 1
g = [[] for _ in range(n)]
a = [0] * n
b = a + []
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	g[u].append(v)
	g[v].append(u)

def bfs(start, x):
	q = [start]
	while len(q) > 0:
		curr = q.pop()
		for adj in g[curr]:
			if not x[adj]:
				x[adj] = x[curr] + 1
				q.insert(0, adj)
	x[start] = 0
bfs(s, a)
bfs(t, b)
cnt = 0
for i in range(n):
	for j in range(i + 1, n):
		if min(a[i] + b[j], a[j] + b[i]) > a[t] - 2:
			cnt += 1
print(cnt - m)


from heapq import *

def dijkstra(st):
	dist = [10 ** 18] * n
	dist[st] = 0
	pq = []
	heappush(pq, (dist[st], st))
	while pq:
		(d, v) = heappop(pq)
		if dist[v] < d:
			continue
		for nv in adj_list[v]:
			if dist[nv] > dist[v] + 1:
				dist[nv] = dist[v] + 1
				heappush(pq, (dist[nv], nv))
	return dist
(n, m, s, t) = map(int, input().split())
adj_list = [[] for _ in range(n)]
exist = [[False] * n for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	adj_list[u - 1].append(v - 1)
	adj_list[v - 1].append(u - 1)
	exist[u - 1][v - 1] = True
	exist[v - 1][u - 1] = True
dist1 = dijkstra(s - 1)
dist2 = dijkstra(t - 1)
D = dist1[t - 1]
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		if not exist[i][j] and dist1[i] + 1 + dist2[j] >= D and (dist1[j] + 1 + dist2[i] >= D):
			ans += 1
print(ans)


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, u, v) = map(int, input().split())
graph = [[] for _ in range(n)]
mtx = [[0] * n for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
	mtx[a][b] = 1
	mtx[b][a] = 1
q = [u - 1]
vec1 = [0] * n
vec1[u - 1] = 1
while q:
	c = q.pop(0)
	for i in graph[c]:
		if not vec1[i]:
			vec1[i] = vec1[c] + 1
			q.append(i)
q = [v - 1]
vec2 = [0] * n
vec2[v - 1] = 1
while q:
	c = q.pop(0)
	for i in graph[c]:
		if not vec2[i]:
			vec2[i] = vec2[c] + 1
			q.append(i)
for i in range(n):
	vec1[i] -= 1
	vec2[i] -= 1
res = 0
for i in range(n):
	for j in range(i + 1, n):
		if not mtx[i][j] and min(vec2[j] + vec1[i] + 1, vec2[i] + vec1[j] + 1) >= vec1[v - 1]:
			res += 1
print(res)


from sys import stdin
from collections import deque

def bfs(x):
	q = deque()
	dis = [0] * (n + 1)
	vis = [False] * (n + 1)
	vis[x] = True
	q.append(x)
	while len(q):
		cur = q.popleft()
		for to in g[cur]:
			if not vis[to]:
				vis[to] = True
				dis[to] = dis[cur] + 1
				q.append(to)
	return dis
(n, m, s, t) = map(int, stdin.readline().split())
g = [[] for _ in range(n + 1)]
for i in range(m):
	(u, v) = map(int, stdin.readline().split())
	g[u].append(v)
	g[v].append(u)
ds = bfs(s)
dt = bfs(t)
ans = 0
for u in range(1, n + 1):
	for v in range(u + 1, n + 1):
		if v not in g[u] and min(ds[u] + dt[v], dt[u] + ds[v]) + 1 >= ds[t]:
			ans += 1
print(ans)


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) = 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) = 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)


import collections
import heapq

def do():
	(nodes, edges, s, t) = map(int, input().split(' '))
	s -= 1
	t -= 1
	g = collections.defaultdict(set)
	for _ in range(edges):
		(x, y) = map(int, input().split(' '))
		x -= 1
		y -= 1
		g[x].add(y)
		g[y].add(x)
	ds = [0] * nodes
	dt = [0] * nodes

	def bfs1(node):
		q = collections.deque()
		q.append((node, 0))
		seen = [0] * nodes
		seen[node] = 1
		while q:
			(cur, cost) = q.popleft()
			ds[cur] = cost
			for nei in g[cur]:
				if not seen[nei]:
					seen[nei] = 1
					q.append((nei, cost + 1))

	def bfs2(node):
		q = collections.deque()
		q.append((node, 0))
		seen = [0] * nodes
		seen[node] = 1
		while q:
			(cur, cost) = q.popleft()
			dt[cur] = cost
			for nei in g[cur]:
				if not seen[nei]:
					seen[nei] = 1
					q.append((nei, cost + 1))
	bfs1(s)
	bfs2(t)
	res = 0
	for i in range(nodes):
		for j in range(i):
			if ds[i] + 1 + dt[j] >= ds[t] and ds[j] + 1 + dt[i] >= ds[t]:
				res += 1
	return res - edges
print(do())


(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)


import sys
import heapq
(nnode, nedge, source, dest) = map(int, sys.stdin.readline().split())
source -= 1
dest -= 1
adjl = [[] for _ in range(nnode)]
for _ in range(nedge):
	(u, v) = map(int, sys.stdin.readline().split())
	u -= 1
	v -= 1
	adjl[u].append(v)
	adjl[v].append(u)

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)


from collections import defaultdict

class Graph:

	def __init__(self):
		self.graph = defaultdict(list)
		self.nodes = []

	def addEdge(self, u, v):
		self.graph[u].append(v)
		self.graph[v].append(u)
		if u not in self.nodes:
			self.nodes.append(u)
		if v not in self.nodes:
			self.nodes.append(v)

	def BFS(self, s, dest):
		visited = [False] * len(self.graph)
		dist = [-1] * len(self.graph)
		queue = []
		queue.append(s)
		visited[s] = True
		dist[s] = 0
		path = 0
		while queue:
			s = queue.pop(0)
			for i in self.graph[s]:
				if visited[i] == False:
					dist[i] = dist[s] + 1
					queue.append(i)
					visited[i] = True
					if i == dest:
						path = dist[i]
		return (dist, path)

	def BFS2(self, s):
		visited = [False] * len(self.graph)
		dist = [-1] * len(self.graph)
		queue = []
		queue.append(s)
		visited[s] = True
		dist[s] = 0
		while queue:
			s = queue.pop(0)
			for i in self.graph[s]:
				if visited[i] == False:
					dist[i] = dist[s] + 1
					queue.append(i)
					visited[i] = True
		return dist

	def count(self, sourcedist, destdist, path):
		opt = 0
		d = -1
		for i in range(len(self.nodes)):
			for j in range(i + 1, len(self.nodes)):
				if j in self.graph[i]:
					continue
				if destdist[i] > destdist[j]:
					d = destdist[j] + sourcedist[i] + 1
				else:
					d = destdist[i] + sourcedist[j] + 1
				if d >= path:
					opt += 1
		print(opt)
inp = input().split()
g = Graph()
for i in range(int(inp[1])):
	edge = input().split()
	g.addEdge(int(edge[0]) - 1, int(edge[1]) - 1)
(sourcedist, path) = g.BFS(int(inp[2]) - 1, int(inp[3]) - 1)
destdist = g.BFS2(int(inp[3]) - 1)
g.count(sourcedist, destdist, path)


import sys
from collections import deque
readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def bfs(G, s, t=None):
	dist = [-1] * len(G)
	dist[s] = 0
	q = deque([s])
	while q:
		v = q.popleft()
		for x in G[v]:
			if dist[x] < 0 or dist[x] > dist[v] + 1:
				dist[x] = dist[v] + 1
				q.append(x)
	if t is None:
		return dist
	else:
		return dist[t]

def solve():
	(n, m, s, t) = nm()
	s -= 1
	t -= 1
	G = [list() for _ in range(n)]
	for _ in range(m):
		(u, v) = nm()
		u -= 1
		v -= 1
		G[u].append(v)
		G[v].append(u)
	dss = bfs(G, s)
	dst = bfs(G, t)
	ans = 0
	sp = dss[t]
	for i in range(n - 1):
		for j in range(i + 1, n):
			if dss[i] + dst[j] + 1 >= sp and dss[j] + dst[i] + 1 >= sp:
				ans += 1
	print(ans - m)
	return
solve()


from collections import deque

def bfs(s, graph):
	q = deque()
	d = [0] * len(graph)
	used = [False] * len(graph)
	used[s] = True
	q.append(s)
	while len(q):
		cur = q[0]
		q.popleft()
		for to in graph[cur]:
			if not used[to]:
				used[to] = True
				d[to] = d[cur] + 1
				q.append(to)
	return d
(n, m, s, t) = map(int, input().split())
graph = [set() for _ in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	graph[u].add(v)
	graph[v].add(u)
ds = bfs(s, graph)
dt = bfs(t, graph)
ans = 0
for u in range(1, n + 1):
	for v in range(u + 1, n + 1):
		if v not in graph[u] and min(ds[u] + dt[v], dt[u] + ds[v]) + 1 >= ds[t]:
			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)


(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)


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def bfs(n, gp, st):
	q = deque([st])
	dist = [-1] * (n + 1)
	dist[st] = 0
	while q:
		node = q.popleft()
		for x in gp[node]:
			if dist[x] == -1:
				dist[x] = dist[node] + 1
				q.append(x)
	return dist

def main():
	try:
		(n, m, st, end) = In()
		gp = defaultdict(set)
		for i in range(m):
			(a, b) = In()
			gp[a].add(b)
			gp[b].add(a)
		bfs1 = bfs(n, gp, st)
		bfs2 = bfs(n, gp, end)
		length = bfs1[end]
		cnt = 0
		for i in range(1, n + 1):
			for j in range(i + 1, n + 1):
				if j in gp[i]:
					continue
				elif bfs1[i] + bfs2[j] + 1 < length:
					continue
				elif bfs1[j] + bfs2[i] + 1 < length:
					continue
				else:
					cnt += 1
		print(cnt)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


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)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
(n, m, s, t) = map(int, input().split())
d = defaultdict(list)
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	d[a].append(b)
	d[b].append(a)

def calc(d, s, t):
	dist = [10 ** 9] * n
	vis = [0] * n
	q = [s]
	dist[s] = 0
	vis[s] = 1
	while q:
		t = q.pop(0)
		for i in d[t]:
			if not vis[i]:
				dist[i] = dist[t] + 1
				vis[i] = 1
				q.append(i)
	return dist
s -= 1
t -= 1
dist_s = calc(d, s, t)
dist_t = calc(d, t, t)
ans = 0
mini = dist_s[t]
(s, t) = (min(s, t), max(s, t))
for i in range(n):
	for j in range(i + 1, n):
		if i not in d[j] and (not (i == s and j == t)):
			psbl1 = dist_s[i] + 1 + dist_t[j]
			psbl2 = dist_t[i] + 1 + dist_s[j]
			m = min(psbl1, psbl2)
			if m >= mini:
				ans += 1
print(ans)


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)


import sys
input = sys.stdin.readline
from collections import deque
(n, m, s, t) = map(int, input().split())
s -= 1
t -= 1
g = [[] for i in range(n)]
gg = [set() for i in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	gg[u - 1].add(v - 1)
	g[v - 1].append(u - 1)
	gg[v - 1].add(u - 1)

def bfs01(x, d):
	dq = deque([x])
	d[x] = 0
	while dq:
		ver = dq.popleft()
		for to in g[ver]:
			if d[to] == -1:
				dq.append(to)
				d[to] = d[ver] + 1
	return d
cnt = 0
d_s = bfs01(s, [-1] * n)
d_t = bfs01(t, [-1] * n)
l = d_s[t]
for i in range(n):
	for j in range(i + 1, n):
		if j in gg[i] or i in gg[j]:
			continue
		if l <= min(l, d_s[i] + 1 + d_t[j], d_s[j] + 1 + d_t[i]):
			cnt += 1
print(cnt)


from collections import defaultdict, deque
from sys import stdin, stdout

def In():
	return map(int, stdin.readline().split())

def bfs(n, graph, start):
	q = deque([start])
	dist = [-1] * (n + 1)
	dist[start] = 0
	while q:
		current = q.popleft()
		for neigh in graph[current]:
			if dist[neigh] == -1:
				dist[neigh] = dist[current] + 1
				q.append(neigh)
	return dist

def main():
	(n, m, s, t) = In()
	graph = defaultdict(set)
	for i in range(m):
		(a, b) = In()
		graph[a].add(b)
		graph[b].add(a)
	ds = bfs(n, graph, s)
	dt = bfs(n, graph, t)
	res = 0
	aim = ds[t]
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			if j not in graph[i]:
				if ds[i] + dt[j] + 1 < aim or ds[j] + dt[i] + 1 < aim:
					continue
				else:
					res += 1
	print(res)
main()