B. Две ярмарки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии $$$n$$$ городов, некоторые пары из которых соединены двусторонними дорогами. Гарантируется, что из любого города можно доехать в любой другой, двигаясь по дорогам. Города пронумерованы от $$$1$$$ до $$$n$$$.

В настоящий момент в Берляндии проходят две ярмарки — они проходят в двух различных городах $$$a$$$ и $$$b$$$ ($$$1 \le a, b \le n$$$; $$$a \ne b$$$).

Найдите количество таких пар городов $$$x$$$ и $$$y$$$ ($$$x \ne a, x \ne b, y \ne a, y \ne b$$$), что двигаясь из $$$x$$$ в $$$y$$$ обязательно придётся проехать через обе ярмарки (порядок их посещения не важен). Формально, надо найти количество таких пар городов $$$x,y$$$, что любой путь из $$$x$$$ в $$$y$$$ проходит и через $$$a$$$ и через $$$b$$$ (в любом порядке).

Выведите искомое количество пар. Порядок двух городов в паре не имеет значение, то есть пары $$$(x,y)$$$ и $$$(y,x)$$$ надо учитывать один раз.

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

В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 4\cdot10^4$$$) — количество наборов входных данных в тесте. Далее записаны $$$t$$$ наборов входных данных.

В первой строке каждого набора содержится четыре целых числа $$$n$$$, $$$m$$$, $$$a$$$ и $$$b$$$ ($$$4 \le n \le 2\cdot10^5$$$, $$$n - 1 \le m \le 5\cdot10^5$$$, $$$1 \le a,b \le n$$$, $$$a \ne b$$$) — количество городов и дорог в Берляндии и номера двух городов, где проходят ярмарки, соответственно.

Следующие $$$m$$$ строк содержат описания дорог между городами. Каждая из них содержит пару целых чисел $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — номера соединенных дорогой городов.

Каждая дорога является двунаправленной, соединяет пару различных городов. Гарантируется, что из любого города можно проехать в любой другой по дорогам. Между парой городов может быть более одной дороги.

Сумма значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2\cdot10^5$$$. Сумма значений $$$m$$$ по всем наборам входных данных в тесте не превосходит $$$5\cdot10^5$$$.

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

Выведите $$$t$$$ целых чисел — ответы на заданные наборы входных данных в порядке их записи в тесте.

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