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;

typedef ostringstream OSS;
typedef istringstream ISS;

typedef long long LL;
typedef pair<int, int> PII;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef vector<VS> VVS;
typedef vector<bool> VB;
typedef vector<VB> VVB;
typedef vector<PII> VPII;

#define fst first
#define snd second
#define MP make_pair
#define PB push_back
#define EB emplace_back 
#define ALL(x) (x).begin(),(x).end()
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

template < typename T > inline T fromString(const string &s) { T res; ISS iss(s); iss >> res; return res; };
template < typename T > inline string toString(const T &a) { OSS oss; oss << a; return oss.str(); };

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

int N, M, s, t;
VVI es;

VI bfs(int p0) {
	VI d(N, INF);
	d[p0] = 0;

	queue<int> q;
	q.push(p0);

	while (q.size()) {
		int p = q.front();
		q.pop();

		int next_cost = d[p] + 1;
		
		for (auto next : es[p]) {
			int &dist = d[next];
			if (next_cost < dist) {
				dist = next_cost;
				q.push(next);
			}
		}
	}

	return d;
}

int main(void) {
	cin >> N >> M >> s >> t;
	--t; --s;
	es.resize(N);
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		es[a].PB(b);
		es[b].PB(a);
	}

	// s, t????????????????????¢?±???????
	VI sd = bfs(s);
	VI td = bfs(t);
	int st = sd[t];

	// ?????¢->?????°?????????
	VI d2c_t(100010);
	for (auto d : td) {
		if (d == INF) continue;
		d2c_t[d]++;
	}

	// count
	LL cnt = 0;
	for (auto d : sd) {
		if (d == INF) continue;
		int idx = st - d - 2;
		if (idx >= 0) {
			cnt += d2c_t[idx];
		}
	}

	cout << cnt << endl;


	return 0;
}