Problem E: SUSTech Tower Defence

Problem E: SUSTech Tower Defence

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 343  Solved: 152
[Submit][Status][Web Board]

Description

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.

Input

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\).

Output

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

4

HINT

[Submit][Status]