eolymp
bolt
Try our new interface for solving problems
Problems

Transport system

Transport system

Time limit 1 second
Memory limit 128 MiB

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, and 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.

Input data

First line contains four integers: number of intersections n~(1 \le n \le 10^3), number of roads m~(1 \le m \le 10^5), intersection s with home, intersection t with work (1 \le s, t \le n, s \ne t). Then m lines are given, i-th line contains two integers u_i and v_i~(1 \le u_i, v_i \le n, u_i \ne v_i). They mean that there is a two-way road between intersections u_i and v_i.

Output data

Print the number of required intersection pairs.

Examples

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

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


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