CF2059D Graph and Graph

题目描述

给定两个具有相同顶点数的连通无向图。在这两个图中，各有一个标记位于某个顶点处。在第一个图中，标记初始位于顶点 $s_1$；在第二个图中，标记初始位于顶点 $s_2$。以下操作将被无限次重复执行：

• 假设当前第一个图中的标记位于顶点 $v_1$，第二个图中的标记位于顶点 $v_2$。
• 在第一个图中选择一个与 $v_1$ 相邻的顶点 $u_1$。
• 在第二个图中选择一个与 $v_2$ 相邻的顶点 $u_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$）——第一个图的边数。

接下来的 $m_1$ 行中，第 $i$ 行包含两个整数 $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$）——第二个图的边数。

接下来的 $m_2$ 行中，第 $j$ 行包含两个整数 $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$。

输入输出样例 #1

输入 #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

输出 #1

0
-1
7

说明/提示

在第一个测试用例中，可以构造标记在两个图中沿着顶点 $2, 3, 4, 1, 2, 3, 4, 1, \ldots$ 无限移动的转移序列。

在第二个测试用例中，可以证明任何操作的代价均大于 $0$，因此所有操作的总代价将无限大。

翻译由 DeepSeek R1 完成