e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

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

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

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

67554986_10162197962520344_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
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
5 4 1 5
1 2
2 3
3 4
4 5
Вихідні дані #1
0
Вхідні дані #2
5 4 3 5
1 2
2 3
3 4
4 5
Вихідні дані #2
5
Вхідні дані #3
5 6 1 5
1 2
1 3
1 4
4 5
3 5
2 5
Вихідні дані #3
3