Minus One

Time Limit : 2 sec, Memory Limit : 131072 KB

イクタ君は、無向グラフについて異常なほどの思い入れを持っている。イクタ君は、無向グラフ G とその 2 点 s,tの組(G,s,t)のうち、その「うつくしさ」が大きいものが好きである。 組(G,s,t)の「うつくしさ」とは、辺 e = \{u, v\} (uvG の異なる 2 点) で、Gにおけるsからtへの最短路の長さが、Geをつけくわえた無向グラフにおける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≤ N ≤ 100,000
  • 1≤ M ≤ 300,000
  • 1≤ s,t,xi,yi ≤ N
  • st とは異なる
  • 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

Source: ACM-ICPC Japan Alumni Group Summer Camp 2013 , Day 3, Tokyo, Japan, 2013-09-22
http://acm-icpc.aitea.net/
http://jag2013summer-day3.contest.atcoder.jp/