题目描述

圖形結構 $G=(V, G)$ 包含一個有限的集合 $V(G)$ 做為節點集合，以及一個無序對的集合 $E(G)$ 作為邊的集合（如圖一）。圖形結構有相當廣泛的應用，例如：交通路網、蛋白質結構的分析、計畫管理評估、都市系統結構分析、半導體晶片設計元件擺放的布線等，使得圖形結構一直是數學家和電腦科學家解決問題的好工具。

:::align{center}

圖一 :::

在數學中，兩個集合 $A$ 和 $B$ 的笛卡兒乘積 (Cartesian product)，在集合論中表示為 $A \times B$，是所有可能的有序對組成的集合，其中有序對的第一個對象是 $A$ 的成員，第二個對象是 $B$ 的成員。圖形理論學家 $Ray$ 教授研究圖形性質多年，他定義兩圖形 $G$ 與 $H$ 的融合圖為一個新的圖形結構並以 $G \times H$ 表示，其點集合為 $V(G) \times V(H)$，此圖形中若兩節點 $(u, v)$ 與 $(u^\prime, v^\prime)$ 相連必須滿足：

• $u = u^\prime$ 且 $\{v, v^\prime\} \in E(H)$，或
• $v = v^\prime$ 且 $\{u, u^\prime\} \in E(G)$。

圖二顯示了圖一中 $G$ 和 $H$ 的笛卡兒乘積。

:::align{center}

圖二 :::

$Ray$ 教授為了要進一步瞭解融合圖的性質，他定義了一些度量方式：圖形中任兩節點 $x$ 和 $y$ 的距離是指從 $x$ 到 $y$ 之間，所經過邊個數最小的路徑其邊的個數。若要計算一張圖的直徑，首先要求得任意兩點之間的最短路徑，在這些所有的最短路徑中，取其長度最長者，即是這張圖的直徑（如圖三）。給定兩張圖形 $G$ 與 $H$，請協助 $Ray$ 教授計算融合圖 $G \times H$ 的直徑。假如答案大於或等於 $10^9+7$，則輸出除以 $10^9+7$ 之後的餘數；若沒有答案，意即存在兩點之間沒有路徑，則輸出 $-1$。

:::align{center}

圖三：此圖直徑為 $2$ :::

输入格式

$$\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$ 代表圖 $G$ 中的節點個數，即 $\left\vert V( G )\right\vert$。
• $e_{i,j}$ 代表圖 $G$ 中，$i$ 和 $j$ 是否相連，其中 $e_{i,j}=1$ 代表有相連，$e_{i,j}=0$ 則代表沒有相連。
• $n_2$ 代表圖 $H$ 中的節點個數，即 $\left\vert V( H )\right\vert$。
• $e^\prime_{i,j}$ 代表圖 $H$ 中，$i$ 和 $j$ 是否相連，其中 $e^\prime_{i,j}=1$ 代表有相連，$e^\prime_{i,j}=0$ 則代表沒有相連。

输出格式

$$D$$

• 如果直徑存在，則 $D$ 代表融合圖 $G\times H$ 的直徑除以 $10^9+7$ 之後的餘數。
• 如果直徑不存在，則 $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

提示

測資限制

• $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}$。
• 保證圖 $G$ 沒有自環，也就是 $\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}$。
• 保證圖 $H$ 沒有自環，也就是 $\forall 1\le i\le n_2, e^\prime_{i,i}=0$。

評分說明

本題共有四組子任務，條件限制如下所示。 定義 $m_1,m_2$ 依序為圖 $G$、圖 $H$ 邊的個數，也就是 $m_1=\left\vert E(G)\right\vert, m_2=\left\vert E(H)\right\vert$。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。

子任務	分數	額外輸入限制
1	18	$n_1, m_1 \leq 400$，$n_2=1$ 且 $m_2=0$。
2	11	保證 $G$ 和 $H$ 都是沒有環的連通圖。
3	25	$m_1, m_2 \leq 4000$。
4	46	無額外限制。