A13113. Two Fairs
编程题
普及/提高-
知识点
题目描述
There are $n$ cities in Berland and some pairs of them are connected by two-way roads. It is guaranteed that you can pass from any city to any other, moving along the roads. Cities are numerated from $1$ to $n$ .
Two fairs are currently taking place in Berland — they are held in two different cities $a$ and $b$ ( $1 \le a, b \le n$ ; $a \ne b$ ).
Find the number of pairs of cities $x$ and $y$ ( $x \ne a, x \ne b, y \ne a, y \ne b$ ) such that if you go from $x$ to $y$ you will have to go through both fairs (the order of visits doesn't matter). Formally, you need to find the number of pairs of cities $x,y$ such that any path from $x$ to $y$ goes through $a$ and $b$ (in any order).
Print the required number of pairs. The order of two cities in a pair does not matter, that is, the pairs $(x,y)$ and $(y,x)$ must be taken into account only once.
Two fairs are currently taking place in Berland — they are held in two different cities $a$ and $b$ ( $1 \le a, b \le n$ ; $a \ne b$ ).
Find the number of pairs of cities $x$ and $y$ ( $x \ne a, x \ne b, y \ne a, y \ne b$ ) such that if you go from $x$ to $y$ you will have to go through both fairs (the order of visits doesn't matter). Formally, you need to find the number of pairs of cities $x,y$ such that any path from $x$ to $y$ goes through $a$ and $b$ (in any order).
Print the required number of pairs. The order of two cities in a pair does not matter, that is, the pairs $(x,y)$ and $(y,x)$ must be taken into account only once.
输入格式
The first line of the input contains an integer $t$ ( $1 \le t \le 4\cdot10^4$ ) — the number of test cases in the input. Next, $t$ test cases are specified.
The first line of each test case contains four integers $n$ , $m$ , $a$ and $b$ ( $4 \le n \le 2\cdot10^5$ , $n - 1 \le m \le 5\cdot10^5$ , $1 \le a,b \le n$ , $a \ne b$ ) — numbers of cities and roads in Berland and numbers of two cities where fairs are held, respectively.
The following $m$ lines contain descriptions of roads between cities. Each of road description contains a pair of integers $u_i, v_i$ ( $1 \le u_i, v_i \le n$ , $u_i \ne v_i$ ) — numbers of cities connected by the road.
Each road is bi-directional and connects two different cities. It is guaranteed that from any city you can pass to any other by roads. There can be more than one road between a pair of cities.
The sum of the values of $n$ for all sets of input data in the test does not exceed $2\cdot10^5$ . The sum of the values of $m$ for all sets of input data in the test does not exceed $5\cdot10^5$ .
The first line of each test case contains four integers $n$ , $m$ , $a$ and $b$ ( $4 \le n \le 2\cdot10^5$ , $n - 1 \le m \le 5\cdot10^5$ , $1 \le a,b \le n$ , $a \ne b$ ) — numbers of cities and roads in Berland and numbers of two cities where fairs are held, respectively.
The following $m$ lines contain descriptions of roads between cities. Each of road description contains a pair of integers $u_i, v_i$ ( $1 \le u_i, v_i \le n$ , $u_i \ne v_i$ ) — numbers of cities connected by the road.
Each road is bi-directional and connects two different cities. It is guaranteed that from any city you can pass to any other by roads. There can be more than one road between a pair of cities.
The sum of the values of $n$ for all sets of input data in the test does not exceed $2\cdot10^5$ . The sum of the values of $m$ for all sets of input data in the test does not exceed $5\cdot10^5$ .
输出格式
Print $t$ integers — the answers to the given test cases in the order they are written in the input.
输入输出样例
输入 #1
3 7 7 3 5 1 2 2 3 3 4 4 5 5 6 6 7 7 5 4 5 2 3 1 2 2 3 3 4 4 1 4 2 4 3 2 1 1 2 2 3 4 1
输出 #1
4 0 1