AT_abc394_e [ABC394E] Palindromic Shortest Path

$ N $ 頂点の有向グラフがあり、頂点には $ 1, 2, \ldots, N $ の番号が付いています。 辺の情報は $ N^2 $ 個の文字 $ C_{1, 1}, C_{1, 2}, \ldots, C_{1, N}, C_{2, 1}, \ldots, C_{N, N} $ によって与えられます。ここで、 $ C_{i, j} $ は英小文字あるいは `-` です。 $ C_{i, j} $ が英小文字のとき頂点 $ i $ から頂点 $ j $ へ向かう辺がちょうど $ 1 $ つ存在してラベル $ C_{i, j} $ が付いており、 $ C_{i, j} $ が `-` のとき頂点 $ i $ から頂点 $ j $ へ向かう辺は存在しません。 $ 1 \leq i, j \leq N $ を満たす各整数組 $ (i, j) $ について、以下の問題に対する答えを求めてください。 - 頂点 $ i $ から頂点 $ j $ に向かう（単純とは限らない）パスのうち、辺に付けられたラベルの文字を順に結合した文字列が回文となるようなものの中で最も短いものの長さを求めよ。ただし、そのようなパスがない場合は答えは $ -1 $ とせよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ C_{1, 1} $ $ C_{1, 2} $ $ \ldots $ $ C_{1, N} $ $ C_{2, 1} $ $ C_{2, 2} $ $ \ldots $ $ C_{2, N} $ $ \vdots $ $ C_{N, 1} $ $ C_{N, 2} $ $ \ldots $ $ C_{N, N} $

整数組 $ (i, j) $ に対する答えを $ A_{i, j} $ として以下の形式で出力せよ。 > $ A_{1, 1} $ $ A_{1, 2} $ $ \ldots $ $ A_{1, N} $ $ A_{2, 1} $ $ A_{2, 2} $ $ \ldots $ $ A_{2, N} $ $ \vdots $ $ A_{N, 1} $ $ A_{N, 2} $ $ \ldots $ $ A_{N, N} $

### Sample Explanation 1 例として $ (i, j) = (1, 4) $ の場合について説明します。 頂点 $ 1 \to 1 \to 2 \to 3 \to 4 $ というパスにおける辺に付けられた文字のラベルを順に結合すると文字列 `abba` が得られます。これは回文であり、頂点 $ 1 $ から頂点 $ 4 $ へ向かう長さ $ 3 $ 以下のパスであって辺に付けられたラベルの文字を順に結合した文字列が回文となるものは存在しないため $ (i, j) = (1, 4) $ に対する答えは $ 4 $ となります。 空文字列も回文であることに注意してください。 ### Constraints - $ 1 \leq N \leq 100 $ - $ N $ は整数 - $ C_{i, j} $ は英小文字あるいは `-`