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