You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在 P 市的交通规划中，有一个复杂而精妙的交通网络。这个庞大的网络涵盖了 $n$ 个交通枢纽，它们通过 $m$ 条纵横交错的道路（均为双向道路）相互紧密连接，形成了一个高效运转的整体。

在这个网络中，枢纽 $a$ 和 $b$ 扮演着极为特殊且关键的角色，它们是城市交通的重要物资中转站，承载着大量物资的调配和运输任务，对整个城市的物资流通起着举足轻重的作用。

现在，为了探究枢纽 $a,b$ 的运输压力以便后续的城市规划，研究员希望探究其他枢纽在物流运输过程中经过 $a,b$ 的情况。也就是在不直接涉及这两个特殊枢纽作为起始点或终点的情况下，研究员试图探究有多少对其他交通枢纽之间的通行路径必然会经过这两个重要的物资中转站。

具体来说，要找出满足以下严格条件的二元组 $(u,v)$ 的数量：

• $1 \le u < v \le n$；
• $u \not= a, v \not= a, u \not= b, v \not= b$；
• 任意一条从 $u$ 到 $v$ 的路径都经过 $a,b$。

请你协助研究员完成这一次调查。

输入格式

输入第一行包含四个整数 $n,m,a,b$，分别表示枢纽数量，道路数量，以及两个重要枢纽的编号。

接下来 $m$ 行，每行两个整数 $u,v$，描述了一条双向道路 $(u,v)$。

保证从任何枢纽，你都可以通过双向道路到达任何其他枢纽，一对枢纽之间可能有不止一条路。

输出格式

输出共一行，表示满足上述要求的 $(u,v)$ 对数。

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

4

样例 1 解释

合法的枢纽对有：$(1,6),(1,7),(2,6),(2,7)$。

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

0

其余样例见下发文件。

junction3.in
junction3.ans
junction4.in
junction4.ans

数据规模与约定

• 对于 $20\%$ 的数据，保证 $n \le 10, m \le 15$。
• 对于 $40\%$ 的数据，保证 $n \le 50,m \le 200$。
• 对于另 $20\%$ 的数据，保证 $m = n - 1$。
• 对于 $100\%$ 的数据，保证 $4 \le n \le 2 \times 10^5,n-1 \le m \le 5 \times 10^5,a \not=b$。