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

Azərbaycan Respublika Olimpiadasının yarımfinalı 2018-2019

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

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

67554986_10162197962520344_3939502891911348224_o.jpg

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

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

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

В первой строке даны четыре целых числа: количество перекрестков n (1n103), количество дорог m (1m105), перекресток s, где находится дом, перекресток t, где находится работа (1s, tn, st). В последующих m строках, i-я строка содержит два числа ui и vi (1ui, vin, uivi). Они означают, что между перекрестками ui и vi имеется двухсторонняя дорога.

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 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
Источник Полуфинал Республиканской олимпиады Азербайджана 2018-2019