问题 4911 --4.路径统计

4911: 4.路径统计

题目描述

  小W所在城市有 $n$ 个学校(编号从 $1$ 到 $n$ ),学校与学校之间用一些双向道路连接。我们已知任意两个学校一定是可以相互到达的(直接或者间接)。
现在有两个学校 $a$ 和 $b (1 \leq a,b \leq n,a \not = b)$ 。假如当前有两个学校 $x$ 和 $y (x \not = a, x \not = b,y \not=a ,y \not =b)$ ,如果我们要从 $x$ 走到 $y$ 一定会经过 $a$ 和 $b$ (经过 $a, b$ 的顺序没有关系),那么我们就把这个 $x$ 和 $y$ 称为一个神奇的点对,注意 $x$ 和 $y$ 交换顺序也只能作为同一个点对。
现在,小W很好奇,他想要知道在这个城市里,这样的神奇点对有多少?
你的任务就是帮小W来统计这些神奇的点对。

输入

输入一行有$4$个正整数$n, m, a, b$ ,分别表示学校的数量,双向道路的数量还有两个特殊的学校 $a$ 和 $b$。
接下来有 $m$ 行,每行两个正整数 $u_i$ 和 $u_i$ ,表示 $u_i$ 和 $v_i$ 之间有一条双向道路,保证没有重复的边,也没有自环。

输出

输出一定要经过学校 $a$ 和 $6$ 的神奇的点对的数量。

样例输入输出

输入#1 复制
7 7 3 5
1 2
2 3
3 4
4 5
5 6
6 7
7 5
输出#1 复制
4
输入#2 复制
4 5 2 3
1 2
2 3
3 4
4 1
4 2
输出#2 复制
0
输入#3 复制
4 3 2 1
1 2
2 3
4 1
输出#3 复制
1

提示

样例1中,(1, 6), (1, 7), (2, 6), (2, 7)都是神奇的点对,因为它们相互到达一定 会经过3和5。
样例2中,没有点对一定会经过2和3。
样例3中,只有点对(3, 4)一定要经过1和2。

对于第1个到第3个测试点,$1 \leq n \leq 1000$,保证 $n-1 = m$ ,保证按 $1$ 到 $n$ 的顺序刚好连成一条直线。
对于第4个到第6个测试点,$1 \leq n \leq 1000$,保证 $n-1= m$,保证刚好是一- 棵树。
对于第7个到第8个测试点,$1 \leq n \leq 5000$, 这个图没有什么特殊性质。
对于所有数据,$1 \leq n \leq 10000,1 \leq a,b \leq n,1 \leq m \leq 20000,a \not= b,u_i \not =v_i$ ,所有的道路均不相同。


序号 标题 作者 发表时间 费用 订购数 操作