Problem 1390 --SUSTech Tower Defence1390: SUSTech Tower Defence
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 347 Solved: 153
[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
Source
[Submit][Status]