问题背景

本故事纯属虚构。

题目描述

公元 $2100$ 年，由于人类破坏了臭氧层，外加太阳系阿尔法伽马射线波影响到地球的表面环境，导致地表变成了一个不适合人类居住的环境。

于是，人类全部迁徙到了地下。

在某国有 $n(2 \le n \le 1000)$ 个地下城市，编号从 $1$ 到 $n$，这些城市之间以隧道连接。两个城市之间最多只有一个隧道，每条隧道都是双向连通的。

该国目前已经建造了 $m(1 \le m \le 10000)$ 条隧道。这些隧道保证 $n$ 个城市连通，也就是说，从任意一个城市都可以通过若干条隧道到达其它任何一个城市。

该国有两个重要城市，经济中心是编号为 $s$ 的城市，娱乐中心是编号为 $t$ 的城市（$1 \le s,t \le n; s \neq t$）。

由于大多数人都生活在城市 $t$，但是都工作在城市 $s$，这就导致早晚高峰的时候从城市 $s$ 到 $t$ 的路线显得拥堵。

为了缓解这个问题，该国的建设部长决定在两个城市间建设一条隧道。但是建设新的隧道收到一些规则的约束。

首先，如果两个城市之间已经有一条现有的隧道了，那么就不能在这两个城市之间再建一条隧道了。

其次，由于每条隧道都是收费的。

每经过一条隧道，就需要缴纳 $1$ 块钱的通行费。

所以新建的隧道还需要满足如下条件：

当新建了隧道后，从城市 $s$ 到城市 $t$ 的所有路线需要缴纳的通行费总和的最小值不会变小。

因为如果新隧道开通后人们从城市 $s$ 经由新隧道到达 $t$ 的通行费总和最小值变少了，一方面会导致其它隧道通行率变低，另一方面也会导致新建的这条隧道变得拥堵。

现在建设部长委托你来确定一下一共有多少种不同的隧道修建方案，同时满足如下两个条件：

• 隧道连接的两个城市之间之前之前没有建设过直接相连的隧道；
• 隧道建成后从城市 $s$ 到城市 $t$ 的所有路线对应的通行费总和的最小值不变。

请你帮助他完成这个工作。

注：对于两个城市来说，连接城市 $u$ 和 $v$ 之间的隧道，和连接城市 $v$ 和 $u$ 之间的隧道视为同一条隧道。

输入格式

输入的第一行包含四个整数 $n, m, s, t$，分别表示城市数量，现有隧道数量，经济中心和娱乐中心对应的城市编号（$1 \le n \le 1000$，$1 \le m \le 10000$，$1 \le s,t \le n$，$s \neq t$）。

接下来 $m$ 行，每一行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示现有一条连接城市 $u_i$ 和 $v_i$ 的隧道。

输出格式

输出一个整数，表示满足题目要求的隧道新建方案数。

5 4 1 5
1 2
2 3
3 4
4 5

0

5 4 3 5
1 2
2 3
3 4
4 5

5

5 6 1 5
1 2
1 3
1 4
4 5
3 5
2 5

3

说明/提示

样例解释

样例1：没有合适的新建方案

样例2：一共有 $5$ 种合适的新建方案：$(1, 3)$，$(1, 4)$，$(1, 5)$，$(2, 4)$，$(2, 5)$

样例3：一共有 $3$ 种合适的新建方案：$(2, 3)$，$(2, 4)$，$(3, 4)$

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 10; m \le 20$
• 对于 $60\%$ 的数据，$n \le 100; m \le 20$
• 对于 $100\%$ 的数据，$2 \le n \le 1000; 1 \le m \le 10000$，数据保证现有的 $m$ 条隧道能保证 $n$ 个城市连通