#215394. [NHSPC 2025] 融合圖的直徑

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

:::align{center}

圖一 :::

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

• 且 ，或
• 且 。

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

:::align{center}

圖二 :::

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

:::align{center}

圖三：此圖直徑為 :::

• 代表圖 中的節點個數，即 。
• 代表圖 中， 和 是否相連，其中 代表有相連， 則代表沒有相連。
• 代表圖 中的節點個數，即 。
• 代表圖 中， 和 是否相連，其中 代表有相連， 則代表沒有相連。

• 如果直徑存在，則 代表融合圖 的直徑除以 之後的餘數。
• 如果直徑不存在，則 。

样例输入 1

2
01
10
2
01
10

样例输出 1

2

样例输入 2

4
0101
1010
0101
1010
4
0100
1011
0100
0100

样例输出 2

4

样例输入 3

5
01000
10101
01010
00101
01010
1
0

样例输出 3

3

測資限制

• 。
• 。
• 。
• 保證圖 沒有自環，也就是 。
• 。
• 。
• 。
• 保證圖 沒有自環，也就是 。

評分說明

本題共有四組子任務，條件限制如下所示。 定義 依序為圖 、圖 邊的個數，也就是 。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。