CF954D.Fight Against Traffic

Little town Nsk consists of n junctions connected by m bidirectional roads. Each road connects two distinct junctions and no two roads connect the same pair of junctions. It is possible to get from any junction to any other junction by these roads. The distance between two junctions is equal to the minimum possible number of roads on a path between them.

In order to improve the transportation system, the city council asks mayor to build one new road. The problem is that the mayor has just bought a wonderful new car and he really enjoys a ride from his home, located near junction s to work located near junction t. Thus, he wants to build a new road in such a way that the distance between these two junctions won't decrease.

You are assigned a task to compute the number of pairs of junctions that are not connected by the road, such that if the new road between these two junctions is built the distance between s and t won't decrease.

小城 Nsk 由 $n$ 个路口和 $m$ 条双向道路组成。每条道路连接两个不同的路口，且任意一对路口之间至多只有一条道路相连。通过这些道路，可以从任意一个路口到达其他任意路口。两个路口之间的距离定义为连接它们的路径上所经过的最少道路数。

为了改善交通系统，市政府要求市长修建一条新道路。然而，市长刚刚购买了一辆极佳的新车，他非常享受从家（位于路口 $s$ 附近）到工作地点（位于路口 $t$ 附近）的驾车过程。因此，他希望新建的道路不会使 $s$ 和 $t$ 之间的距离减小。

你的任务是：计算有多少对尚未由道路直接连接的路口，使得若在它们之间修建一条新道路，则 $s$ 与 $t$ 之间的距离不会减小。

The firt line of the input contains integers n, m, s and t (2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000, 1 ≤ s, t ≤ n, s ≠ t) — the number of junctions and the number of roads in Nsk, as well as the indices of junctions where mayors home and work are located respectively. The i-th of the following m lines contains two integers u__i and v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i), meaning that this road connects junctions u__i and v__i directly. It is guaranteed that there is a path between any two junctions and no two roads connect the same pair of junctions.

输入的第一行包含整数 $n$、$m$、$s$ 和 $t$（$2 ≤ n ≤ 1000$，$1 ≤ m ≤ 1000$，$1 ≤ s, t ≤ n$，且 $s ≠ t$），分别表示 Nsk 市的路口数量、道路数量，以及市长家和工作地点所在的路口编号。接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 ≤ u_i, v_i ≤ n$，且 $u_i ≠ v_i$），表示该道路直接连接路口 $u_i$ 和 $v_i$。保证任意两个路口之间均存在路径，且不存在两条道路连接同一对路口。

Print one integer — the number of pairs of junctions not connected by a direct road, such that building a road between these two junctions won't decrease the distance between junctions s and t.

输出一个整数——表示不直接相连的路口对的数量，使得在这些路口之间修建一条道路不会缩短路口 $s$ 与 $t$ 之间的距离。