e-olymp
Competitions

Полуфинал Республиканской олимпиады Азербайджана 2018-2019

Транспортная Система

Транспортная система города Баку состоит из N перекрестков и из M двухсторонних дорог, соединяющих эти перекрестки. Каждая дорога соединяет ровно два перекрестка, и никакая пара перекрестков не может быть соединена больше, чем одной дорогой. Перемещаясь по этим дорогам, можно поехать с любого перекрестка на любой другой. Расстоянием между двумя перекрестками считается минимальное количество дорог среди всех путей, соединяющих эти перекрестки.

67554986<em>10162197962520344</em>3939502891911348224_o.jpg

Чтобы улучшить транспортную систему, мер города потребовал у директора транспортной системы провести новую дорогу. Однако, мер купил новую машину и каждый день наслаждается поездкой из дома на работу и с работы домой. Ему не хочется, чтобы уменьшилось расстояние между перекрестком s, где находится его дом и перекрестком t, где находится его работа. Помогите директору транспортной системы решить эту задачи, так как он обязательно должен выполнить требование мера. Ваша задача найти количество таких пар несоединенных перекрестков, что проведя дорогу между этими перекрестками, расстояние между перекрестками s и t не уменьшится.

Входные данные

В первой строке даны четыре целых числа, разделенных пробелом: N – количество перекрестков, M – количество дорог, s – перекресток, где находится дом, t – перекресток, где находится работа. В последующих M строках, i-я строка содержит два числа разделенных пробелом – ui и vi. Это означает, что между перекрестками ui и vi есть двухсторонняя дорога.

Выходные данные

Выведите искомое в условии задачи количество пар перекрестков.

Ограничения

  • 1 ≤ N ≤ 103
  • 1 ≤ M ≤ 105
  • 1 ≤ s, t ≤ N, s ≠ t
  • 1 ≤ ui, vi ≤ N, ui ≠ vi
Time limit 1 second
Memory limit 64 MiB
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
Input example #3
5 6 1 5
1 2
1 3
1 4
4 5
3 5
2 5
Output example #3
3