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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from collections import deque, defaultdict
(n, m, s, t) = map(int, input().split())
s -= 1
t -= 1
edges = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	edges[x].append(y)
	edges[y].append(x)

def dist_from(s):
	INF = 10 ** 20
	dist = [INF] * n
	dist[s] = 0
	que = deque()
	que.append((0, s))
	while que:
		(score, node) = que.popleft()
		for to in edges[node]:
			if dist[to] > score + 1:
				dist[to] = score + 1
				que.append((score + 1, to))
	return dist
dist_from_s = dist_from(s)
dic1 = {}
for (i, d) in enumerate(dist_from_s):
	if d in dic1:
		dic1[d].add(i)
	else:
		dic1[d] = {i}
dist_from_t = dist_from(t)
dic2 = {}
for (i, d) in enumerate(dist_from_t):
	if d in dic2:
		dic2[d].add(i)
	else:
		dic2[d] = {i}
st_dist = dist_from_s[t]
ans = 0
for key in dic1:
	another_key = st_dist - key - 2
	if another_key in dic2:
		add = len(dic1[key]) * len(dic2[another_key])
		for u in dic1[key]:
			for to in edges[u]:
				if to in dic2[another_key]:
					add -= 1
		ans += add
print(ans)


import heapq

def dijkstra_heap(s):
	d = [float('inf')] * n
	used = [True] * n
	d[s] = 0
	used[s] = False
	edgelist = []
	for e in edge[s]:
		heapq.heappush(edgelist, e)
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		d[v] = minedge[0]
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, (e[0] + d[v], e[1]))
	return d
(n, w, s, t) = map(int, input().split())
edge = [[] for i in range(n)]
for i in range(w):
	(x, y) = map(int, input().split())
	edge[x - 1].append((1, y - 1))
	edge[y - 1].append((1, x - 1))
(a, b) = ([0] * n, [0] * n)
x = dijkstra_heap(s - 1)
y = dijkstra_heap(t - 1)
distance = x[t - 1] - 1
for t in x:
	if t < n:
		a[t] += 1
for t in y:
	if t < n:
		b[t] += 1
ans = 0
for i in range(distance + 1):
	if distance - i > 0:
		ans += a[i] * b[distance - i - 1]
print(ans)


import heapq
MAX = 2147483647

def dijkstra(dist, start):
	Q = []
	dist[start] = 0
	heapq.heappush(Q, (0, start))
	while Q:
		(t, s) = heapq.heappop(Q)
		if dist[s] < t:
			continue
		for e in to[s]:
			nt = t + 1
			if dist[e] > nt:
				dist[e] = nt
				heapq.heappush(Q, (nt, e))
(N, M, s, t) = map(int, input().split())
(s, t) = (s - 1, t - 1)
to = [[] for i in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	to[x].append(y)
	to[y].append(x)
smin = [MAX] * N
dijkstra(smin, s)
tmin = [MAX] * N
dijkstra(tmin, t)
scnt = [0] * N
tcnt = [0] * N
for i in range(N):
	if smin[i] < N:
		scnt[smin[i]] += 1
	if tmin[i] < N:
		tcnt[tmin[i]] += 1
ans = 0
s = smin[t] - 1
for i in range(s):
	ans += scnt[i] * tcnt[s - 1 - i]
print(ans)


import queue
(n, m, s, t) = map(int, input().split())
table = [[] for i in range(n)]
inf = 300001
dist_s = [inf for i in range(n)]
dist_t = [inf for i in range(n)]
s_list = [0 for i in range(inf + 1)]
t_list = [0 for i in range(inf + 1)]
s -= 1
t -= 1
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	table[a].append(b)
	table[b].append(a)
dist_s[s] = 0
q = queue.Queue()
q.put(s)
while not q.empty():
	p = q.get()
	for e in table[p]:
		if dist_s[e] > dist_s[p] + 1:
			dist_s[e] = dist_s[p] + 1
			q.put(e)
dist_t[t] = 0
q = queue.Queue()
q.put(t)
while not q.empty():
	p = q.get()
	for e in table[p]:
		if dist_t[e] > dist_t[p] + 1:
			dist_t[e] = dist_t[p] + 1
			q.put(e)
for i in range(n):
	s_list[dist_s[i]] += 1
	t_list[dist_t[i]] += 1
mindist = dist_s[t]
ans = 0
for i in range(mindist - 1):
	ans += s_list[i] * t_list[mindist - 2 - i]
print(ans)


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

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

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

def C():
	n = I()
	if n == 0:
		print(1)
	elif n == 1:
		print(2)
	elif n == 2:
		print(1)
	else:
		print(0)
	return

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

def E():
	return

def F():
	return

def G():
	return

def H():
	return

def I_():
	return

def J():
	return
D()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

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

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	(n, m, s, t) = LI()
	xy = [LI() for _ in range(m)]
	e = collections.defaultdict(list)
	for (x, y) in xy:
		e[x].append((y, 1))
		e[y].append((x, 1))

	def search(s):
		d = collections.defaultdict(lambda : inf)
		d[s] = 0
		q = []
		heapq.heappush(q, (0, s))
		v = collections.defaultdict(bool)
		while len(q):
			(k, u) = heapq.heappop(q)
			if v[u]:
				continue
			v[u] = True
			for (uv, ud) in e[u]:
				if v[uv]:
					continue
				vd = k + ud
				if d[uv] > vd:
					d[uv] = vd
					heapq.heappush(q, (vd, uv))
		return d
	d1 = search(s)
	d2 = search(t)
	tt = d1[t]
	if tt == 1:
		return 0
	if tt == 2:
		return 1
	v1 = collections.defaultdict(int)
	v2 = collections.defaultdict(int)
	for (k, v) in d1.items():
		v1[v] += 1
	for (k, v) in d2.items():
		v2[v] += 1
	r = 0
	for i in range(tt - 1):
		r += v1[i] * v2[tt - i - 2]
	return r
print(main())


(N, M, s, t) = map(int, input().split())
E = [[] for _ in range(N + 1)]
for _ in range(M):
	(x, y) = map(int, input().split())
	E[x].append(y)
	E[y].append(x)
closed = [False] * (N + 1)
closed[s] = True
dist = [float('inf')] * (N + 1)
q = [s]
for dist_ in range(N):
	q_new = []
	for v in q:
		dist[v] = dist_
		for u in E[v]:
			if closed[u]:
				continue
			closed[u] = True
			q_new.append(u)
	q = q_new
	if len(q) == 0:
		break
dist_st = dist[t]
closed = [False] * (N + 1)
closed[t] = True
dist_t = [float('inf')] * (N + 1)
q = [t]
for dist_ in range(N):
	q_new = []
	for v in q:
		dist_t[v] = dist_
		for u in E[v]:
			if closed[u]:
				continue
			closed[u] = True
			q_new.append(u)
	q = q_new
	if len(q) == 0:
		break
ds = [0] * (dist_st - 1)
dt = [0] * (dist_st - 1)
for d in dist:
	if d < dist_st - 1:
		ds[d] += 1
for d in dist_t:
	if d < dist_st - 1:
		dt[d] += 1
ans = 0
for (a, b) in zip(ds, dt[::-1]):
	ans += a * b
print(ans)