问题2489--lhx家门口的路

2489: lhx家门口的路

[命题人 : ]
时间限制 : 1 sec  内存限制 : 512 MB

提交

题目描述

lhx有一张无向图,一上面共有 n 个点,由 $m$ 条边连接起来,现在要在任意一对没有连边的点之间连上一条边,并且保证 s t 之间的最短路径长度不变(最短路径长度表示 s t 最少经过的边的数量)和图为简单图(无重边,无自环),请你帮帮lhx求出一共有多少条这样的边。

输入

第一行输入四个整数 n,m,s,t(2<=n<=100),1 <= m <= 1000),1 <= s,t <= n,s 不等于 t)。

 

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

输出

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

样例输入 Copy

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

样例输出 Copy

0