题目描述

题意描述

给你一张无向图，一共有 $n$ 个点（$2 \leq n \leq 1000$），由 $m$ 条边连接起来（$1 \leq m \leq 10000$），现在要在任意一对没有连边的点之间连上一条边,并且保证 $s$ 到 $t$ 之间的最短路径长度不变（最短路径长度表示 $s$ 到 $t$ 最少经过的边的数量）和图为简单图（无重边,无自环）（$1 \leq s,t \leq n$，$s \neq t$），请你求出一共有多少条这样的边。

输入格式

第一行输入四个整数 $n,m,s,t$。

第二行到第 $m+1$ 行每行共有两个数，表示这两个点之间有一条边。

输出格式

一共一行，表示合法的加边方案数。

感谢@zhaotiensn 提供的翻译

样例

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