Problem Description

A graph structure $G = (V, E)$ consists of a finite set $V(G)$ as the set of vertices, and a set $E(G)$ of unordered pairs as the set of edges (as shown in Figure 1). Graph structures have very wide applications, such as transportation networks, protein structure analysis, project management evaluation, urban system structure analysis, and routing for component placement in semiconductor chip design. Therefore, graph structures have always been a useful tool for mathematicians and computer scientists to solve problems.

:::align{center}

Figure 1 :::

In mathematics, the Cartesian product of two sets $A$ and $B$, denoted in set theory as $A \times B$, is the set of all possible ordered pairs, where the first element of the ordered pair is a member of $A$ and the second element is a member of $B$. Professor $Ray$, a graph theorist who has studied graph properties for many years, defined the Cartesian product graph of two graphs $G$ and $H$ as a new graph structure denoted by $G \times H$, whose vertex set is $V(G) \times V(H)$. In this graph, two vertices $(u, v)$ and $(u^\prime, v^\prime)$ are adjacent if and only if:

• $u = u^\prime$ and $\{v, v^\prime\} \in E(H)$, or
• $v = v^\prime$ and $\{u, u^\prime\} \in E(G)$.

Figure 2 shows the Cartesian product of $G$ and $H$ in Figure 1.

:::align{center}

Figure 2 :::

To further understand the properties of the Cartesian product graph, Professor $Ray$ defined some measures: the distance between any two vertices $x$ and $y$ in a graph is the number of edges in the shortest path from $x$ to $y$, i.e., the minimum number of edges among all paths from $x$ to $y$. To compute the diameter of a graph, one must first find the shortest paths between every pair of vertices. Among all these shortest paths, the one with the greatest length is the diameter of the graph (as shown in Figure 3). Given two graphs $G$ and $H$, please help Professor $Ray$ compute the diameter of the Cartesian product graph $G \times H$. If the answer is greater than or equal to $10^9+7$, output the remainder after dividing by $10^9+7$. If there is no answer, meaning there exists a pair of vertices with no path between them, output $-1$.

:::align{center}

Figure 3: The diameter of this graph is $2$ :::

Input Format

$$\begin{aligned} &n_1 \\ &e_{1,1} e_{1,2} \dots e_{1,n_1} \\ &e_{2,1} e_{2,2} \dots e_{2,n_1} \\ &\vdots \\ &e_{n_1,1} e_{n_1,2} \dots e_{n_1,n_1} \\ &n_2 \\ &e^\prime_{1,1} e^\prime_{1,2} \dots e^\prime_{1,n_2} \\ &e^\prime_{2,1} e^\prime_{2,2} \dots e^\prime_{2,n_2} \\ &\vdots \\ &e^\prime_{n_2,1} e^\prime_{n_2,2} \dots e^\prime_{n_2,n_2} \end{aligned}$$

• $n_1$ is the number of vertices in graph $G$, i.e., $\left\vert V( G )\right\vert$.
• $e_{i,j}$ indicates whether $i$ and $j$ are adjacent in graph $G$. $e_{i,j}=1$ means they are adjacent, and $e_{i,j}=0$ means they are not adjacent.
• $n_2$ is the number of vertices in graph $H$, i.e., $\left\vert V( H )\right\vert$.
• $e^\prime_{i,j}$ indicates whether $i$ and $j$ are adjacent in graph $H$. $e^\prime_{i,j}=1$ means they are adjacent, and $e^\prime_{i,j}=0$ means they are not adjacent.

Output Format

$$D$$

• If the diameter exists, then $D$ is the remainder of the diameter of the Cartesian product graph $G \times H$ after dividing by $10^9+7$.
• If the diameter does not exist, then $D = -1$.

2
01
10
2
01
10

2

4
0101
1010
0101
1010
4
0100
1011
0100
0100

4

5
01000
10101
01010
00101
01010
1
0

3

Hint

Constraints

• $1 \leq n_1 \leq 2000$.
• $e_{i,j} \in \lbrace 0, 1 \rbrace$.
• $\forall 1 \leq i < j \leq n_1, e_{i,j}=e_{j,i}$.
• It is guaranteed that graph $G$ has no self-loops, i.e., $\forall 1\le i\le n_1, e_{i,i}=0$.
• $1 \leq n_2 \leq 2000$.
• $e^\prime_{i,j} \in \lbrace 0, 1 \rbrace$.
• $\forall 1 \leq i < j \leq n_2, e^\prime_{i,j}=e^\prime_{j,i}$.
• It is guaranteed that graph $H$ has no self-loops, i.e., $\forall 1\le i\le n_2, e^\prime_{i,i}=0$.

Scoring

This problem has four subtasks, with the constraints shown below.
Let $m_1, m_2$ be the number of edges in graphs $G$ and $H$, respectively, i.e., $m_1=\left\vert E(G)\right\vert, m_2=\left\vert E(H)\right\vert$.
Each subtask may contain one or more testdata files. You will get the score for a subtask only if you solve all testdata in that subtask.

Subtask	Score	Additional Input Constraints
1	18	$n_1, m_1 \leq 400$, $n_2=1$ and $m_2=0$.
2	11	It is guaranteed that both $G$ and $H$ are connected acyclic graphs.
3	25	$m_1, m_2 \leq 4000$.
4	46	No additional constraints.

Translated by ChatGPT 5