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

vector<int> bfs(vector<vector<int> > &G, int s) {  
  vector<int> d(G.size(), -1);  
  queue<int> Q;
  Q.push(s);
  d[s] = 0;
  while ( !Q.empty() ) {
    int v = Q.front(); Q.pop();

    for ( int u : G[v] ) {
      if ( d[u] >= 0 ) continue;
      d[u] = d[v]+1;
      Q.push(u);      
    }    
  }

  return d;  
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, M, s, t;
  cin >> N >> M >> s >> t;
  s--; t--;

  vector<vector<int> > G(N);
  for ( int i = 0; i < M; i++ ) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    G[x].emplace_back(y);
    G[y].emplace_back(x);    
  }

  vector<int> ds = bfs(G, s);
  vector<int> dt = bfs(G, t);
  vector<int> cnts(N, 0), cntt(N, 0);  
  for ( int i = 0; i < N; i++ ) {
    if ( ds[i] >= 0 ) cnts[ds[i]]++;
    if ( dt[i] >= 0 ) cntt[dt[i]]++;    
  }

  int ans = 0;
  int mi = ds[t];
  for ( int i = 0; i < N; i++ ) {    
    if ( mi-i-2 >= 0 ) ans += cnts[i] * cntt[mi-i-2];    
  }

  cout << ans << endl;
  
  return 0;
}