← 返回题目列表

Codeforces · 2059/D

D. 图与图

中文机器翻译题面 查看原题

给您两个具有相同顶点数的连通无向图。在这两个图中,都有一个标记位于某个顶点。在第一个图中,令牌最初位于顶点 $$$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

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$$$;因此,所有操作的总成本将无限大。