给您两个具有相同顶点数的连通无向图。在这两个图中,都有一个标记位于某个顶点。在第一个图中,令牌最初位于顶点 $$$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$$$;因此,所有操作的总成本将无限大。