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
#define DBG 0
#define dump(o) if(DBG){cerr<<#o<<" "<<(o)<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

using Weight = int;
class Edge {
public:
	int s; //source
	int d; //destination
	Weight w; //weight
	Edge(int s = 0, int d = 0, Weight w = INF) : s(s), d(d), w(w) {};
	bool operator<(const Edge &e)const { return w < e.w; }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

//?????¢?´¢, ??¢?´¢???, ??¢?´¢???
enum { WHITE, GRAY, BLACK };
//???????§?????????????(???????????????) Single Source Shortest Path
//Dijkstra O( |E|log|V| )
//dist: ?§????????????????????????§??????????????¢
//?????????: ???????????¨????????????(??????-1)
vector<int> dijkstra(const Graph &g, int s, vector<Weight> &dist) {
	typedef tuple<Weight, int, int> State; //?§?????????????????°?????????? ??? ???
	priority_queue<State, vector<State>, greater<State> >PQ;
	int n = g.size();
	vector<int> color(n, WHITE);
	vector<int> prev(n, -1);
	dist.assign(n, INF); //distance
	dist[s] = 0; PQ.emplace(0, s, -1); color[s] = GRAY; //?§????
	while (!PQ.empty()) {
		Weight d; int v; int u;
		tie(d, v, u) = PQ.top(); PQ.pop(); //dist???????°??????¨??????????´????????????????
		if (dist[v] < d) continue; //?????§???????????§???????????°??????
		color[v] = BLACK;
		prev[v] = u;
		for (auto &e : g[v]) { //??£??\????????????????????¨????????????		
			if (color[e.d] == BLACK)continue; //??¢?´¢????????????
			if (dist[e.d] > dist[v] + e.w) {
				dist[e.d] = dist[v] + e.w;
				PQ.emplace(dist[e.d], e.d, v);
				color[e.d] = GRAY;
			}
		}
	}
	return prev;
}

signed main() {
	int N, M, s, t; cin >> N >> M >> s >> t; s--, t--;
	Graph G(N);
	rep(i, 0, M) {
		int x, y; cin >> x >> y; x--, y--;
		G[x].emplace_back(x, y, 1);
		G[y].emplace_back(y, x, 1);
	}
	vector<int> dist;
	dijkstra(G, s, dist);
	dumpc(dist);
	int mi = dist[t];

	vector<int> cnt(N, 0);
	for (auto &d : dist)if (d < N)cnt[d]++;

	dumpc(cnt);
	vector<int> dist2;
	dijkstra(G, t, dist2);
	dumpc(dist2);
	vector<int> cnt2(N, 0);
	for (auto &d : dist2)if (d < N)cnt2[d]++;
	dumpc(cnt2);

	int ans = 0;
	rep(i, 0, mi - 1) {
		ans += cnt[i] * cnt2[mi - 1 - i - 1];
		dump(ans);
	}
	cout << ans << endl;
	return 0;
}