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

Solution:
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(_v) for(auto _x:_v){cout<<_x<<" ";}cout<<endl
#define printVS(_vs) for(auto _x : _vs){cout << _x << endl;}
#define printVV(_vv) for(auto _v:_vv){for(auto _x:_v){cout<<_x<<" ";}cout<<endl;}
#define printP(_p) cout << _p.first << " " << _p.second << endl
#define printVP(_vp) for(auto _p : _vp) printP(_p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

// undirected
void addEdge(Graph& G, int x, int y) {
    G[x].emplace_back(y);
    G[y].emplace_back(x);
}

vector<int> bfs(const Graph& G, int s) {
	int n = G.size();
    vector<int> d(n, inf);
	queue<int> que;
    que.push(s);
    d[s] = 0;

    while (!que.empty()) {
        int pre = que.front(); que.pop();
        for (auto nxt: G[pre]) {
            if (d[nxt] == inf) {
                que.push(nxt);
                d[nxt] = d[pre] + 1;
            }
        }
    }

    return d;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--; t--;
    Graph G(n);
    rep(i, m) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        addEdge(G, x, y);
    }


    auto d1 = bfs(G, s);
    auto d2 = bfs(G, t);
    int D = d1[t];

    if (D == 1) {
        cout << 0 << endl;
        return 0;
    }

    vi c1(n);
    vi c2(n);

    rep(i, n) {
        if (d1[i] == inf) continue;
        c1[d1[i]]++;
    }
    rep(i, n) {
        if (d2[i] == inf) continue;
        c2[d2[i]]++;
    }

    int ans = 0;
    for (int i = 0, j = D - 2; j >= 0; i++, j--) {
        ans += c1[i] * c2[j];
    }

    rep(i, n) {
        for (auto j : G[i]) {
            if (i < j) continue;
            if (d1[i] + d2[j] == D - 2 || d2[i] + d1[j] == D - 2) {
                ans--;
            }
        }
    }

    cout << ans << endl;

}