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:
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

struct edge{int to, cost;};

int n, d[100010];
vector<edge> g[100010];

void dijkstra(int s) {
  priority_queue<PII, vector<PII>, greater<PII>> que;
  fill(d, d+n, INF);
  d[s] = 0;
  que.push(PII{0, s});

  while(que.size()) {
    PII p = que.top(); que.pop();
    // cout << p.first << "," << p.second << endl;
    int v = p.second;
    if(d[v] < p.first) continue;
    for(edge e: g[v]) {
      // cout << d[e.to] << ":" << d[v] << ":" << e.cost << endl;
      if(d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        que.push(PII{d[e.to], e.to});
      }
    }
  }
}

int cnt1[300010], cnt2[300010];
signed main(void)
{
  int m, s, t;
  cin >> n >> m >> s >> t;
  s--, t--;
  REP(i, m) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    g[x].PB({y, 1});
    g[y].PB({x, 1});
  }

  dijkstra(s);
  // REP(i, n) cout << d[i] << " "; cout << endl;
  int dist = d[t]-1;
  REP(i, n) if(d[i] != INF) cnt1[d[i]]++;
  dijkstra(t);
  REP(i, n) if(d[i] != INF) cnt2[d[i]]++;

  // cout << dist << endl;
  ll ret = 0;
  REP(i, dist) {
    // cout << i << "," << cnt1[i] << " " << dist-i-1 << "," << cnt2[dist-i-1] << endl;
    ret += cnt1[i] * cnt2[dist-i-1];
  }
  cout << ret << endl;

  return 0;
}