favorite We need a little bit of your help to keep things running, click on this banner to learn more

Shortest paths - interesting graph problems

Transport system

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 (1n103), number of roads m (1m105), intersection s with home, intersection t with work (1s, tn, st). Then m lines are given, i-th line contains two integers ui and vi (1ui, vin, uivi). They mean that there is a two-way road between intersections ui and vi.


Print the number of required intersection pairs.


Time limit 1 second
Memory limit 128 MiB
Input example #1
5 4 1 5
1 2
2 3
3 4
4 5

Output example #1
Input example #2
5 4 3 5
1 2
2 3
3 4
4 5

Output example #2
Source 2018-2019 Republic Azerbaijan, Semifinals