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

Вам даны два связных неориентированных графа с одинаковым количеством вершин. В обоих графах в какой-то вершине находится фишка. В первом графе фишка изначально находится в вершине $$$s_1$$$, во втором графе фишка изначально находится в вершине $$$s_2$$$. Далее бесконечное количество раз повторяются следующая операция:

  • Пусть сейчас в первом графе фишка находится в вершине $$$v_1$$$, а во втором графе в вершине $$$v_2$$$.
  • Выбирается какая-то вершина $$$u_1$$$, смежная с $$$v_1$$$, в первом графе.
  • Выбирается какая-то вершина $$$u_2$$$, смежная с $$$v_2$$$, во втором графе.
  • Фишки перемещаются в выбранные вершины: в первом графе фишка перемещается из $$$v_1$$$ в $$$u_1$$$, во втором графе из $$$v_2$$$ в $$$u_2$$$.
  • Стоимость такой операции равна $$$|u_1 - u_2|$$$.

Определите минимально возможную суммарную стоимость всех операций или сообщите, что это значение будет бесконечно большим.

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

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

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$s_1$$$ и $$$s_2$$$ ($$$2 \le n \le 1000$$$, $$$1 \le s_1, s_2 \le n$$$) — количество вершин в каждом графе, номер вершины в первом графе, где изначально находится фишка, и номер вершины во втором графе, где изначально находится фишка.

Вторая строка каждого набора входных данных содержит одно целое число $$$m_1$$$ ($$$1 \le m_1 \le 1000$$$) — количество рёбер в первом графе.

$$$i$$$-я из следующих $$$m_1$$$ строк содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$) — номера концов $$$i$$$-го ребра в первом графе.

Следующая строка каждого набора входных данных содержит одно целое число $$$m_2$$$ ($$$1 \le m_2 \le 1000$$$) — количество рёбер во втором графе.

$$$j$$$-я из следующих $$$m_2$$$ строк содержит два целых числа $$$c_j$$$ и $$$d_j$$$ ($$$1 \le c_j, d_j \le n$$$, $$$c_j \ne d_j$$$) — номера концов $$$j$$$-го ребра во втором графе.

Гарантируется, что сумма $$$n$$$, сумма $$$m_1$$$ и сумма $$$m_2$$$ по всем наборам входных данных не превосходят $$$1000$$$.

Гарантируется, что оба графа являются связными.

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

Для каждого набора входных данных выведите одно целое число — минимальную суммарную стоимость всех операций или $$$-1$$$, если это значение будет бесконечно большим.

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

В первом наборе входных данных можно построить бесконечную последовательность переходов в вершины $$$2, 3, 4, 1, 2, 3, 4, 1, \ldots$$$, по которой фишка может двигаться как в первом, так и во втором графе.

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