Shortest paths - interesting graph problems
The transport system of Baku consists of n intersections and m two-way roads connecting these intersections. Each road connects exactly two intersections, and no pair of intersections can be connected by more than one road. Moving along these roads, you can go from any intersection to any other. The distance between two intersections is the minimum number of roads among all paths connecting these intersections.
To improve the transport system, the city mayor demanded that the director of the transport system must build a new road. However, mayor bought a new car and every day enjoys a trip from home to work and from work home. He does not want the distance between the intersection s where his house is located and the intersection t where his work is located to be reduced. Help the director of the transport system to solve this problem, an to fulfill the requirement of the mayor.
Your task is to find the number of pairs of unconnected intersections that, having travelled between them, the distance between the intersections s and t will not decrease.
First line contains four integers: number of intersections n (1 ≤ n ≤
103), number of roads m (1 ≤ m ≤
105), intersection s with home, intersection t with work (1 ≤ s, t ≤ n, s ≠ t). Then m lines are given, i-th line contains two integers
vi (1 ≤
vi ≤ n,
vi). They mean that there is a two-way road between intersections
Print the number of required intersection pairs.
5 4 1 5 1 2 2 3 3 4 4 5
5 4 3 5 1 2 2 3 3 4 4 5