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 <vector>
#include <queue>
using namespace std;

int main() {

  long long int n, m, s, t;
  cin >> n >> m >> s >> t;

  s--;
  t--;

  vector< vector< long long int > > v;
  vector< long long int > cs;
  vector< long long int > ct;

  for ( long long int i = 0; i < n; i++ ) {
    vector< long long int > vv;
    v.push_back( vv );
    cs.push_back( m + 10 );
    ct.push_back( m + 10 );
  }

  for ( long long int i = 0; i < m; i++ ) {

    long long int x, y;
    cin >> x >> y;
    x--;
    y--;
    v[x].push_back( y );
    v[y].push_back( x );

  }

  vector< vector< long long int > > ps;
  vector< vector< long long int > > pt;
  for ( long long int i = 0; i <= m; i++ ) {
    vector< long long int > vs;
    ps.push_back( vs );
    vector< long long int > vt;
    pt.push_back( vt );
  }


  queue< long long int > q;
  q.push( t );
  ct[t] = 0;
  pt[0].push_back( t );

  while( q.size() > 0 ) {

    long long int k = q.front();
    q.pop();

    for ( long long int i = 0; i < v[k].size(); i++ ) {

      if ( ct[ v[k][i] ] > m ) {
	ct[ v[k][i] ] = ct[k] + 1;
	q.push( v[k][i] );
	pt[ ct[ v[k][i] ] ].push_back( v[k][i] );
      }

    }

  }


  q.push( s );
  cs[s] = 0;
  ps[0].push_back( s );

  while( q.size() > 0 ) {

    long long int k = q.front();
    q.pop();

    for ( long long int i = 0; i < v[k].size(); i++ ) {

      if ( cs[ v[k][i] ] > m ) {
	cs[ v[k][i] ] = cs[k] + 1;
	q.push( v[k][i] );
	ps[ cs[ v[k][i] ] ].push_back( v[k][i] );
      }

    }

  }


  long long int ans = 0;

  long long int k = cs[t] - 2;

  for ( long long int i = 0; i <= k; i++ ) {

    ans += ps[i].size() * pt[k-i].size();

  }

  cout << ans << endl;

  return 0;

}