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 $。

在第一个测试用例中，可以构造标记在两个图中沿着顶点 $ 2, 3, 4, 1, 2, 3, 4, 1, \ldots $ 无限移动的转移序列。 在第二个测试用例中，可以证明任何操作的代价均大于 $ 0 $，因此所有操作的总代价将无限大。 翻译由 DeepSeek R1 完成