Time Limit: 2 sec / Memory Limit: 128 MB
イクタ君は、無向グラフについて異常なほどの思い入れを持っている。イクタ君は、無向グラフ G とその 2 点 s,tの組(G,s,t)のうち、その「うつくしさ」が大きいものが好きである。 組(G,s,t)の「うつくしさ」とは、辺 e = \{u, v\} (u と v は G の異なる 2 点) で、Gにおけるsからtへの最短路の長さが、Gにeをつけくわえた無向グラフにおけるsからtへの最短路の長さより 1 だけ大きいものの個数である。
あなたの仕事は、組(G,s,t)が与えられたとき、その「うつくしさ」を求めるプログラムを書くことである。
Input
入力は以下の形式で与えられる。
N M s t
x1 y1
...
xi yi
...
xM yM
最初に無向グラフの頂点数、辺数、2つの頂点を表す整数N,M,s,tが入力される。 2行目からM+1行目までは辺によって結ばれている2つの頂点が入力される。 (ただし、G の頂点集合を\{1,..., N\}とする。)
Constraints
入力中の各変数は以下の制約を満たす。
2\leq N \leq 100,000
1\leq M \leq 300,000
1\leq s,t,xi,yi \leq N
s と t とは異なる
s から t に辿り着けることは保証されている
Output
与えられたグラフをGとしたとき、組(G,s,t)の「うつくしさ」を1行で出力せよ。
Sample Input 1
3 2 1 3 1 2 2 3
Output for the Sample Input 1
1
頂点1から頂点3に辺を張ると、2点間の最短距離が 1 短くなる。
Sample Input 2
9 8 7 8 2 6 4 9 8 6 9 2 3 8 1 8 8 5 7 9
Output for the Sample Input 2
7
Sample Input 3
4 3 1 4 1 2 3 4 4 1
Output for the Sample Input 3
0
頂点1と頂点4には既に辺が張られているので、これ以上距離を縮めることはできない。
Sample Input 4
9 7 8 9 9 6 6 5 3 6 3 7 2 5 8 5 1 4
Output for the Sample Input 4
2