Graph and Graph
Contest: Codeforces Round 1002 (Div. 2)
Difficulty rating: 1900
Tags: data structures, graphs, greedy, shortest paths

You are given two connected undirected graphs with the same number of vertices. In both graphs, there is a token located at some vertex. In the first graph, the token is initially at vertex $$$s_1$$$, and in the second graph, the token is initially at vertex $$$s_2$$$. The following operation is repeated an infinite number of times:

- Let the token currently be at vertex $$$v_1$$$ in the first graph and at vertex $$$v_2$$$ in the second graph.
- A vertex $$$u_1$$$, adjacent to $$$v_1$$$, is chosen in the first graph.
- A vertex $$$u_2$$$, adjacent to $$$v_2$$$, is chosen in the second graph.
- The tokens are moved to the chosen vertices: in the first graph, the token moves from $$$v_1$$$ to $$$u_1$$$, and in the second graph, from $$$v_2$$$ to $$$u_2$$$.
- The cost of such an operation is equal to $$$|u_1 - u_2|$$$.

Determine the minimum possible total cost of all operations or report that this value will be infinitely large.

Input format:
Each test consists of multiple test cases. The first line contains one integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$s_1$$$, and $$$s_2$$$ ($$$2 \le n \le 1000$$$, $$$1 \le s_1, s_2 \le n$$$) — the number of vertices in each graph, the number of the vertex in the first graph where the token is initially located, and the number of the vertex in the second graph where the token is initially located.

The second line of each test case contains one integer $$$m_1$$$ ($$$1 \le m_1 \le 1000$$$) — the number of edges in the first graph.

The $$$i$$$-th of the following $$$m_1$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$) — the numbers of the endpoints of the $$$i$$$-th edge in the first graph.

The next line of each test case contains one integer $$$m_2$$$ ($$$1 \le m_2 \le 1000$$$) — the number of edges in the second graph.

The $$$j$$$-th of the following $$$m_2$$$ lines contains two integers $$$c_j$$$ and $$$d_j$$$ ($$$1 \le c_j, d_j \le n$$$, $$$c_j \ne d_j$$$) — the numbers of the endpoints of the $$$j$$$-th edge in the second graph.

It is guaranteed that the sum of $$$n$$$, the sum of $$$m_1$$$, and the sum of $$$m_2$$$ over all test cases do not exceed $$$1000$$$.

It is guaranteed that both graphs are connected.

Output format:
For each test case, output one integer — the minimum total cost of all operations or $$$-1$$$, if this value will be infinitely large.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, an infinite sequence of transitions can be constructed to the vertices $$$2, 3, 4, 1, 2, 3, 4, 1, \ldots$$$, along which the token can move in both the first and the second graphs.

In the second test case, it can be proven that the cost of any operation will be greater than $$$0$$$; therefore, the total cost of all operations will be infinitely large.

Example input:
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

Example output:
0
-1
7

Editorial:
First, we need to understand when the answer is less than infinity. For this to happen, the first token in the first graph must be at vertex $$$v$$$, and the second token in the second graph must also be at the vertex with the same number $$$v$$$. Additionally, there must be an identical edge from $$$v$$$ to $$$u$$$ in both graphs for some $$$u$$$. If we find ourselves in such a situation, the tokens (each in their respective graph) can move along this edge back and forth as many times as needed with a cost of $$$0$$$. Let's first identify all the vertices $$$v$$$ (which we will call good) that have this property, and then we will calculate the minimum cost to reach any of these vertices.
We will create a new graph where each vertex corresponds to a specific state, and the edges represent transitions between states. We will define a state as a pair $$$v_1, v_2$$$, which indicates that the first token is currently at vertex $$$v_1$$$, and the second token is at vertex $$$v_2$$$. The number of vertices in this graph will be $$$n^2$$$. A vertex will have $$$deg(v_1) \cdot deg(v_2)$$$ edges (where $$$deg(v)$$$ is the degree of $$$v$$$ in the graph where this vertex is located). Given the overall constraint on the sum of $$$deg(v)$$$, the number of edges in the new state graph will not exceed $$$m_1 \cdot m_2$$$. Let's run Dijkstra's algorithm on this graph and take the distance to the pair of good vertices.