题解

思路推导

回文串的首尾字符相同。设当前已经从原路径的两端分别走到了顶点 $u$ 和 $v$，若从 $u$ 走一条字符为 $c$ 的边到 $x$，同时从 $v$ 走一条字符同为 $c$ 的边到 $y$，就在回文串两端增加了相同字符。

因此可以把状态记为有序点对 $(u,v)$。初始状态是 $(1,N)$，每次同时沿两条字符相同的边移动。每次状态转移对应原路径长度增加 $2$。

当两端来到同一顶点时，可以直接合并，得到偶数长度的回文路径；当两端之间存在一条边时，可以把这条边作为中心，得到奇数长度的回文路径。

做法

对点对状态做 BFS。令 $d(u,v)$ 表示从 $(1,N)$ 到达 $(u,v)$ 至少需要多少次双端移动。

从状态 $(u,v)$ 出发，枚举 $u$ 的邻边和 $v$ 的邻边。只有两条边字符相同时，才能转移到对应的新点对。第一次到达某个状态时的距离最小。

对每个已到达状态检查两种中心：

• 若 $u=v$，用 $2d(u,v)$ 更新答案；
• 若 $u$ 与 $v$ 之间有边，用 $2d(u,v)+1$ 更新答案。

若没有任何状态可以形成中心，则答案为 $-1$。

正确性证明

每次状态转移都在当前字符串的左右两端加入同一个字符，所以从初始状态到任意状态的转移序列都对应一段左右字符完全镜像的路径。

若最终状态满足 $u=v$，两侧路径在同一顶点相接，得到长度为 $2d(u,v)$ 的回文串；若 $u,v$ 之间有边，把该边放在中心，得到长度为 $2d(u,v)+1$ 的回文串。因此算法找到的每个候选答案都合法。

反过来，任意一条从 $1$ 到 $N$ 的回文路径，都可以不断删去首尾两条字符相同的边。若长度为偶数，最后两端停在同一顶点；若长度为奇数，最后剩下一条连接两端的中心边。删边过程正好对应点对图中的一条状态路径，所以算法一定会考察到该回文路径对应的中心状态。

BFS 保证每个状态的双端移动次数最小，再对所有可能中心取最小值，故所得答案是最短回文路径长度。

复杂度分析

点对状态至多有 $N^2$ 个。按字符分组枚举两端邻边后，所有状态转移的总量不超过各字符端点出现次数平方之和，数量级为 $O(M^2)$。时间复杂度为 $O(N^2+M^2)$，空间复杂度为 $O(N^2+M)$。