D. Мета-граф
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан связный неориентированный простой граф $$$G$$$ с $$$n$$$ вершинами и $$$m$$$ рёбрами. Определим его мета-граф $$$f(G)$$$ следующим образом:

  • $$$f(G)$$$ имеет $$$n^2$$$ вершин, обозначенных как $$$a_b$$$ для $$$1\le a, b\le n$$$.
  • Для каждого ребра $$$(a, b)$$$ в $$$G$$$ добавим в $$$f(G)$$$ рёбра $$$(c_a, c_b)$$$ для всех $$$1\le c\le n$$$, а также добавим ребро $$$(a_b, b_a)$$$ в $$$f(G)$$$.

Даны две вершины $$$w_x$$$ и $$$y_z$$$. Требуется определить количество рёбер в кратчайшем пути между ними в $$$f(G)$$$.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$n - 1 \le m\le \min\left(2\cdot 10^5, \frac{n(n-1)}{2}\right)$$$) — количество вершин и количество рёбер в $$$G$$$.

Вторая строка содержит четыре целых числа $$$w$$$, $$$x$$$, $$$y$$$ и $$$z$$$ ($$$1\le w, x, y, z\le n$$$) — начальную вершину $$$w_x$$$ и конечную вершину $$$y_z$$$, соответственно.

Следующие $$$m$$$ строк содержат по два целых числа $$$a$$$ и $$$b$$$ ($$$1\le a \lt b\le n$$$) — рёбра графа $$$G$$$. Гарантируется, что ни одно ребро не встречается более одного раза и что $$$G$$$ связен.

Гарантируется, что суммы $$$n$$$ и $$$m$$$ по всем наборам входных данных не превосходят $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число: количество рёбер на кратчайшем пути от $$$w_x$$$ до $$$y_z$$$ в $$$f(G)$$$. Можно показать, что при условиях задачи между ними всегда существует хотя бы один путь.

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

В первом примере кратчайший (и единственный) путь: $$$1_1, 1_2, 2_1, 2_2, 2_3, 3_2, 3_3$$$.

Мета-граф для первого примера.

Во втором примере кратчайший путь: $$$1_1, 1_4, 4_1$$$.