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 <sstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define Fi first
#define Se second
#define INF (1LL<<60)
#define EPS 1e-10
#define MOD 1000000007
typedef long long ll;
typedef pair<ll, ll> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;


ll N, M;
vector<ll>G[100005];

vector<ll> dijkstra(ll s)
{
  vector<ll>d(N, INF);

  priority_queue<pi, vector<pi>, greater<pi> >Q;
  Q.push(pi(0, s));
  d[s] = 0;
  while(!Q.empty()){
    pi p = Q.top(); Q.pop();
    ll n = p.second;
    if(d[n] < p.first) continue;
    for(auto g:G[n]){
      if(d[g] > d[n] + 1){
	Q.push(pi(d[n]+1, g));
	d[g] = d[n] + 1;
      }
    }
  }
  return d;
}

int main()
{
  ll s, t;
  scanf("%lld%lld%lld%lld", &N, &M, &s, &t); s--; t--;
  rep(i, M){
    ll x, y; scanf("%lld%lld", &x, &y); x--; y--;
    G[x].push_back(y);
    G[y].push_back(x);
  }

  vector<ll>S = dijkstra(s);
  vector<ll>T = dijkstra(t);
  map<ll, ll>dist1;
  multiset<ll>dist2;
  for(auto x: S){
    if(dist1.count(x)) dist1[x] = dist1[x] + 1;
    else dist1[x] = 1;
  }
  for(auto x: T) dist2.insert(x);

  ll d = S[t];
  ll res = 0;
  for(auto x: dist1){
    //    cout << x << " " << d - x - 2 << " " << dist.count(d-x-2) << endl;
    res += x.second*dist2.count(d - x.first - 2);
  }
  printf("%lld\n", res);
  return 0;
}