Alice lives in a city having stations connected by railway tracks. Each track connects two distinct stations and no two tracks connect the same pair of stations. We can go from any station to any station where , 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 and the office station .
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 and won't decrease.
Note: There always exists a path between station to station , where .
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 and .
Constraints
For test case :
The distance between to is . We can connect the stations and . Station and can't be connected by a new track because it will decrease the distance from station to from to . Hence, the answer is .
For test case :
There are railway tracks between and . The distance between to is . We can connect stations . A new track can't connect stations and because it will decrease the distance from station to from to . Hence, the answer is .
For test case :
The distance between to is . We can't add new track between any pair of stations as it will decrease the distance from station to . Hence, the answer is 0.