Вам даны два связных неориентированных графа с одинаковым количеством вершин. В обоих графах в какой-то вершине находится фишка. В первом графе фишка изначально находится в вершине \(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|\).
Определите минимально возможную суммарную стоимость всех операций или сообщите, что это значение будет бесконечно большим.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальную суммарную стоимость всех операций или \(-1\), если это значение будет бесконечно большим.
Примечание
В первом наборе входных данных можно построить бесконечную последовательность переходов в вершины \(2, 3, 4, 1, 2, 3, 4, 1, \ldots\), по которой фишка может двигаться как в первом, так и во втором графе.
Во втором наборе входных данных можно доказать, что стоимость любой операции будет больше \(0\), поэтому суммарная стоимость всех операций будет бесконечно большой.
Примеры
| № | Входные данные | Выходные данные |
|
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
|