eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Транспортна cистема

Транспортна cистема

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Транспортна система міста Баку складається з n перехресть і m двосторонніх доріг, що з'єднують ці перехрестя. Кожна дорога з'єднує рівно два перехрестя, і жодна пара перехресть не може бути з'єднана більше ніж однією дорогою. Переміщаючись цими дорогами, можна поїхати з будь-якого перехрестя на будь-який інший. Відстанню між двома перехрестями вважається мінімальна кількість доріг серед усіх шляхів, що з'єднують ці перехрестя.

Щоб покращити транспортну систему, мер міста зажадав у директора транспортної системи провести нову дорогу. Однак, мер купив нову машину і щодня насолоджується поїздкою з дому на роботу та з роботи додому. Йому не хочеться, щоб зменшилася відстань між перехрестям s, де знаходиться його будинок та перехрестям t, де знаходиться його робота. Допоможіть директору транспортної системи вирішити цю задачу, оскільки він обов'язково має виконати вимогу мера.

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

Вхідні дані

У першому рядку дано чотири цілих числа: кількість перехресть n~(1 \le n \le 10^3), кількість доріг m~(1 \le m \le 10^5), перехрестя s, де знаходиться будинок, перехрестя t, де знаходиться робота (1 \le s, t \le n, s \ne t). У наступних рядках m, i-й рядок містить два числа u_i і v_i~(1 \le u_i, v_i \le n, u_i \ne v_i). Вони означають, що між перехрестями u_i та v_i є двостороння дорога.

Вихідні дані

Виведіть кількість пар перехресть, які потрібно знайти відповідно до умови задачі.

Приклад

Вхідні дані #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