Transport system#9635
The transportation system of the city of Baku consists of intersections and bidirectional roads connecting them. Each road connects exactly two intersections, and there can be at most one road between any pair of intersections. Moreover, it is possible to travel between any two intersections using the existing roads.
The distance between two intersections is defined as the minimum number of roads among all possible paths connecting them.
The city mayor has decided to improve the transportation system and has instructed the director of the transportation department to build a new road. However, the mayor recently bought a new car and enjoys driving from home to work and back every day. He does not want the distance between intersection , where his home is located, and intersection , where his workplace is located, to decrease after the new road is built.
Help the director of the transportation department determine how many pairs of unconnected intersections exist such that if a road is built between them, the distance between and will not decrease.
The first line contains four integers:
n\ (1 \le n \le 10^3) — the number of intersections,
m\ (1 \le m \le 10^5) — the number of roads,
— the intersection where the mayor's home is located,
t\ (1 \le s, t \le n, s \ne t) — the intersection where the mayor's workplace is located.
The next lines each contain two integers u_i and v_i\ (1 \le u_i, v_i \le n, u_i \ne v_i), indicating that there is a bidirectional road between intersections u_i and v_i.
Print the number of pairs of unconnected intersections such that adding a road between them will not decrease the distance between intersections and .
Example 1
Example 2