Problem KW: 路径统计cx201904

Problem KW: 路径统计cx201904

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

SubmitProblemList

Description

小W所在的城市有n个学校(编号从1到n),学校与学校之间用一些双向道路连接。我们已知任意两个学校一定是可以相互到达的(直接或间接)。

现在有两个学校a和b(1≤a,b≤n,a≠b)。假如当前有两个学校x和y(x≠a,x≠b,y≠a,y≠b),如果我们要从x走到y一定会经过a和b(经过a,b的顺序没有关系),那么我们就把这个x和y称为一个神奇的点对,注意x和y交换顺序也只能作为同一个点对。

现在,小W很好奇,他想要知道在这个城市里,这样的神奇点对有多少个?

你的任务就是帮助小W来统计这些神奇的点对。

Input

输入一行有4个正整数n,m,a,b,分别表示学校的数量,双向道路的数量还有两个特殊的学校a和b。

接下来有m行,每行连个正整数vi和ui,表示ui和vi之间有一条双向道路,保证没有重复的边,也没有自环

Output

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

Sample Input Copy

【输入样例1】
7 7 3 5
1 2
2 3
3 4
4 5
5 6
6 7
7 5

【输入样例2】
4 5 2 3
1 2
2 3
3 4
4 1
4 2

【输入样例3】
4 3 2 1
1 2
2 3
4 1

Sample Output Copy

【输出样例1】
4

【输出样例2】
0

【输出样例3】
1

HINT

【样例1解释】

(1,6),(1,7),(2,6),(2,7)都是神奇的点对,因为它们相互到达一定经过3和5.

【样例2解释】

没有点对一定会经过2和3.

【样例3解释】

只有点对(3,4)一定要经过1和2.

【数据范围】

对于第1个到第3个测试点,1≤n≤1000,保证n-1=m,保证按1到n的顺序刚好连成一条直线。

对于第4个到第6个测试点,1≤n≤1000,保证n-1=m,保证刚好是一棵树。

对于第7个到第8个测试点,1≤n≤5000,这个图没有什么特殊性质

对于所有数据,1≤n≤100000,1≤a,b≤n,1≤m≤200000,a≠b,ui≠vi,所有的道路均不相同。