D. Борьба с пробками
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Город Nск состоит из n перекрёстков, соединённых m двунаправленными дорогами. Каждая дорога соединяет какие-то два различных перекрёстка, причём никакие две дороги не соединяют одну и ту же пару перекрёстков. Гарантируется, что от любого перекрёстка можно добраться до любого другого, используя только данные дороги. Расстоянием между двумя перекрёстками называется минимальное количество дорог на пути между ними.

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

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

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

В первой строке входных данных записаны числа n, m, s и t (2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000, 1 ≤ s, t ≤ n, s ≠ t) — количество перекрёстков и количество дорог в городе Nске, а также номера перекрёстков рядом с которыми расположены дом и мэрия соответственно. В i-й из последующих m строк записаны два целых числа ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi), означающих, что перекрёстки ui и vi соединены дорогой напрямую. Гарантируется, что между любой парой перекрёстков существует не более одной прямой дороги, и что, используя данные дороги, можно добраться от любого перекрёстка до любого другого.

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

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

Примеры
Входные данные
5 4 1 5
1 2
2 3
3 4
4 5
Выходные данные
0
Входные данные
5 4 3 5
1 2
2 3
3 4
4 5
Выходные данные
5
Входные данные
5 6 1 5
1 2
1 3
1 4
4 5
3 5
2 5
Выходные данные
3