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 reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
vector<int> used1,used2;
vector<int> dp1,dp2;
priority_queue<pair<int,int>> pq1;
priority_queue<pair<int,int>> pq2;
vector<vector<int>> v;
int main(){
    int n,m;
    int s,t;
    cin>>n>>m>>s>>t;
    s--;
    t--;
    v=vector<vector<int>>(n);
    // set<pair<int,int>> se;
    rep(i,m){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        v[a].push_back(b);
        v[b].push_back(a);
        // se.insert(minmax(a,b));
    }
    used1=vector<int>(n+10,-1);
    used2=vector<int>(n+10,-1);
    pq1.push(make_pair(0,s));
    pq2.push(make_pair(0,t));
    while(pq1.size()){
        auto top=pq1.top();
        pq1.pop();
        if(used1[top.second]>=0) continue;
        used1[top.second]=-top.first;
        for(int x:v[top.second]){
            if(used1[x]>=0) continue;
            pq1.push(make_pair(top.first-1,x));
        }
    }
    while(pq2.size()){
        auto top=pq2.top();
        pq2.pop();
        if(used2[top.second]>=0) continue;
        used2[top.second]=-top.first;
        for(int x:v[top.second]){
            if(used2[x]>=0) continue;
            pq2.push(make_pair(top.first-1,x));
        }
    }
    // for(auto x:se){
    //     cout<<x.first<<" "<<x.second<<endl;
    // }
    long long ans=0;
    int dist=used1[t];
    // if(dist<2){
        // cout<<0<<endl;
        // return 0;
    // }
    dp1=vector<int>(n+10,0);
    dp2=vector<int>(n+10,0);
    rep(i,n){
        if(0<=used1[i]&&used1[i]<=n) dp1[used1[i]]++;
        if(0<=used2[i]&&used2[i]<=n) dp2[used2[i]]++;
    }
    rep(i,dist-1){
        // if(i==dist-2-i) ans+=dp1[i]*dp2[dist-2-i]/2;
        ans+=(long long)dp1[i]*dp2[dist-2-i];
    }
    // rep(i,n){
        // cout<<i<<" "<<used1[i]<<" "<<used2[i]<<endl;
        // if(s==i||t==i) continue;
        // if(used2[i]==dist-2&&se.find(minmax(s,i))==se.end()) ans++;
        // if(used1[i]==dist-2&&se.find(minmax(t,i))==se.end()) ans++;
    // }
    cout<<ans<<endl;
}