Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dfs and similar

dsu

graphs

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Two Fairs

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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.

Input

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$$$.

Output

Print $$$t$$$ integers — the answers to the given test cases in the order they are written in the input.

Example

Input

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

Output

4 0 1

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/02/2023 18:20:08 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|