13901390 SUSTech Online Judge
Problem 1390 --SUSTech Tower Defence

1390: SUSTech Tower Defence

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 347  Solved: 153
[Submit][Status][Web Board]


Two players are playing a game named "SUSTech Tower Defence". One player should choose two cities \(a\), \(b\) to defend and then any soldiers cannot go through these two cities. The job of the other player is to choose as many pairs \((u,v)\) as possible so that he/she can go to \(v\) starting from \(u\) without passing the cities \(a\), \(b\).
Here comes a question - how many pairs \((u,v)\) (\(u\le v\)) are there where we cannot go to \(v\) from \(u\) without passing both of the cities \(a\), \(b\)?
Come and help them.
The given graph is an undirected graph.
It is guaranteed that from any city you can pass to any other by roads.


Line 1: Four integers \(n(2\le n\le10^5)\), \(m(n-1\le m\le10^5)\), \(a(1\le a\le n)\) and \(b(1\le b\le n)\), where \(n\)is the number of nodes, \(m\) is the number of undirected edges, \(a\) and \(b\) are two cities to be defended.
There are \(m\) lines following:
Line 2~(m+1): Two integers \(u\) and \(v\), which means there is an undirected edge between \(u\) and \(v\).


One integer represents the answer to the question.

Sample Input

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

Sample Output