← 返回题目列表

Codeforces · 954/D

D. 对抗交通

中文机器翻译题面 查看原题

小镇 Nsk 由 n 个交叉路口组成,由 m 个双向道路连接。每条道路连接两个不同的路口,并且没有两条道路连接同一对路口。可以通过这些道路从任何路口前往任何其他路口。两个交叉点之间的距离等于它们之间的路径上可能的最小道路数量。

为了改善交通系统,市议会要求市长修建一条新道路。问题是市长刚刚买了一辆很棒的新车,他真的很喜欢从位于 s 路口附近的家到位于 t 路口附近的工作地点。因此,他想修建一条新路,使这两个路口之间的距离不会缩短。

您被分配一项任务来计算未通过道路连接的路口对的数量,这样,如果在这两个路口之间修建新道路,则 s 和 t 之间的距离不会减少。

输入

输入的第一行包含整数 n、m、s 和 t (2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000, 1 ≤ s, t ≤ n, s ≠ t)——Nsk 的路口数量和道路数量,以及市长家庭和工作所在地的路口索引。接下来m行中的第i行包含两个整数ui和vi(1≤ui,vi≤n,ui≠vi),意味着这条路直接连接路口ui和vi。保证任意两个路口之间都有一条路径,并且没有两条道路连接同一对路口。

输出

打印一个整数 - 未通过直接道路连接的路口对的数量,这样在这两个路口之间修建道路不会减少路口 s 和 t 之间的距离。

示例

输入 #1

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

输出 #1

0

输入 #2

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

输出 #2

5

输入 #3

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

输出 #3

3