Station Pairs | Practice Problems

Station Pairs

★★★★★

2 votes

Algorithms, Graphs, Breadth-first search

Details

Submissions

Discussion

Editorial

Problem

Alice lives in a city having $N$ stations connected by $M$ railway tracks. Each track connects two distinct stations and no two tracks connect the same pair of stations. We can go from any station $i$ to any station $j$ where $1 \leq i,j \leq N$ , if there is a railway track between them. The distance between two stations is the minimum possible number of railway tracks on the path between them.

Alice wants to add one new track in the city. But she does not want to decrease the distance between her home station $X$ and the office station $Y$ .

Alice gave you a task to find the number of unordered pairs of two distinct stations that are not connected initially, such that if the new track between these two stations is built, the distance between stations $X$ and $Y$ won't decrease.

Note: There always exists a path between station $i$ to station $j$ , where $1 \leq i,j \leq N$ .

Input format

The first line contains an integer $T$ , denoting the number of test cases.
The first line of each test case contains four integers $N$ , $M$ , $X$ and $Y$ , denoting the total number of stations, the railway tracks, the home and office stations respectively.
The next $M$ lines represent the two integers $A$ and $B$ , such that there is a railway track from station $A$ to station $B$ .

Output format

For each test case, find the total number of pairs of stations, such that adding a new track does not decrease the distance between $X$ and $Y$ .

Constraints

$1 \leq T \leq 10 \\ 1 \leq N, M \leq 10^5 \\ 1 \leq X, Y \leq N \\ 1 \leq A, B \leq N \\ X \neq Y \\ A \neq B$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For test case $1$ :

The distance between $X$ to $Y$ is $2$ . We can connect the stations $(1,3), (1,4), (1,5), (2,5)$ and $(2,4)$ . Station $3$ and $5$ can't be connected by a new track because it will decrease the distance from station $X$ to $Y$ from $2$ to $1$ . Hence, the answer is $5$ .

For test case $2$ :

There are railway tracks between $(1,2), (2,3), (1,3)$ and $(3,4)$ . The distance between $X$ to $Y$ is $2$ . We can connect stations $(2,4)$ . A new track can't connect stations $1$ and $4$ because it will decrease the distance from station $X$ to $Y$ from $2$ to $1$ . Hence, the answer is $1$ .

For test case $3$ :

The distance between $X$ to $Y$ is $3$ . We can't add new track between any pair of stations as it will decrease the distance from station $X$ to $Y$ . Hence, the answer is 0.