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≤i,j≤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≤i,j≤N.
Input format
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≤T≤101≤N,M≤1051≤X,Y≤N1≤A,B≤NX≠YA≠B
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.