Problem E: SUSTech Tower Defence

## Problem E: 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.

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

4

[Submit][Status]