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$ 的边，且该边的标签为 $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}$

约束条件

• $1 \leq N \leq 100$
• $N$ 为整数
• $C_{i, j}$ 为小写字母或 -

样例解释 1

以 $(i, j) = (1, 4)$ 为例：路径 $1 \to 1 \to 2 \to 3 \to 4$ 的边标签组成的字符串为 abba，这是一个回文。由于不存在长度小于 $4$ 的满足条件的路径，因此 $(i, j) = (1, 4)$ 的答案为 $4$。注意空字符串也被视为回文。

翻译由 DeepSeek R1 完成