22443번 - Minus One 다국어

イクタ君は、無向グラフについて異常なほどの思い入れを持っている。イクタ君は、無向グラフ $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)$が与えられたとき、その「うつくしさ」を求めるプログラムを書くことである。

入力は以下の形式で与えられる。

$N$ $M$ $s$ $t$

$x_1$ $y_1$

...

$x_i$ $y_i$

...

$x_M$ $y_M$

最初に無向グラフの頂点数、辺数、2つの頂点を表す整数$N,M,s,t$が入力される。 2行目から$M+1$行目までは辺によって結ばれている2つの頂点が入力される。 (ただし、$G$ の頂点集合を$\{1,..., N\}$とする。)

与えられたグラフを$G$としたとき、組$(G,s,t)$の「うつくしさ」を1行で出力せよ。

入力中の各変数は以下の制約を満たす。

• $2\leq N \leq 100,000$

• $1\leq M \leq 300,000$

• $1\leq s,t,x_i,y_i \leq N$

• $s$ と $t$ とは異なる

• $s$ から $t$ に辿り着けることは保証されている