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 <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long>vll;
typedef pair<int,int> pi;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;


using type = long long;
using P = pair<type, type>;
struct Edge{
    int to, cost;
    Edge(int a, long long b){
        to = a;
        cost = b;
    }
};

class Dijkstra{
private:
    const type _INF = 100000000;
    int V; // 頂点数
    vector<type> d;
    vector<int> prev;
    vector<vector<Edge> > G;
public:
    Dijkstra(int v){
        V = v + 1;
        d.resize(V);
        G.resize(V);
        prev.resize(V);
    }

    void shortest_path(int s){
        priority_queue<P, vector<P>, greater<P>> que;
        d.assign(V, _INF);
        prev.assign(V, -1);
        d[s] = 0;
        que.push(P(0, s));
        while(que.size()){
            P p = que.top(); que.pop();
            int v = p.second;
            if(d[v] < p.first) continue;
            for(auto e : G[v]){
                if(d[v] + e.cost < d[e.to]){
                    d[e.to] = d[v] + e.cost;
                    prev[e.to] = v;
                    que.push(P(d[e.to], e.to));
                }
            }
        }
    }
    
    void add_path(int from, int to, type cost){
        G[from].push_back(Edge(to, cost));
    }

    type get_cost(int t){
        return d[t];
    }

    bool enable_move(int t){
        return d[t] != _INF;
    }
  
    vector<int> get_path(int t){
        vector<int> path;
        for(; t != -1; t = prev[t])
            path.push_back(t);
        reverse(path.begin(), path.end());
        return path;
    }
};

int main(){
  int n,m,s,t;
  cin>>n>>m>>s>>t;

  Dijkstra ds(n),dt(n);
  vector<int> x(m),y(m); 
  for(int i=0;i<m;i++){
    cin>>x[i]>>y[i];
    ds.add_path(x[i],y[i],1);
    ds.add_path(y[i],x[i],1);
    dt.add_path(x[i],y[i],1);
    dt.add_path(y[i],x[i],1);    
  }
  ds.shortest_path(s);
  dt.shortest_path(t);

  ll ds_cost[300005]={0};
  for(int i=1;i<n+1;i++){
    if(ds.enable_move(i))ds_cost[ds.get_cost(i)]++;
  }

  ll dt_cost[300005]={0};
  for(int i=1;i<n+1;i++){
    if(dt.enable_move(i))dt_cost[dt.get_cost(i)]++;
  }

  ll min_cost=ds.get_cost(t);
  ll ans=0;
  for(int i=0;i<min_cost-1;i++){
    ans+=(ds_cost[i]*dt_cost[min_cost-2-i]);
  }
  
  cout<<ans<<endl;
  return 0;
}