頂点 \(1\) と頂点 \(N\) に \(1\) つずつ駒を置いて、「\(2\) つの駒を、同じ文字が書かれた辺を使ってそれぞれ隣接する頂点に動かす」ことを繰り返してだんだん近づけていくイメージで考えます。
偶数長の回文は、これを繰り返して \(2\) つの駒が同じ頂点に来るまでの最小移動回数が求まればよく、奇数長の回文も \(2\) つの駒の距離がちょうど \(1\) になるまでの最小移動回数が求まればよいです。
これを計算するため、元のグラフの \(2\) つの頂点の組 \((a, b)\) すべてに対応する頂点が存在する \(N^2\) 頂点のグラフを考えます。\((a, b)\) に対応する頂点から \((c, d)\) に対応する頂点に辺を張るのは元のグラフにおいて \(a\) と \(c\)、\(b\) と \(d\) の間に辺があり、この \(2\) つの辺に書かれた文字が同じ場合です。
辺の数は合計で \(O(\sum_a \sum_b (\mathrm{deg}(a)\mathrm{deg}(b))) = O(\sum_a (\mathrm{deg}(a) M)) = O(M^2)\) となるので簡単に陽にグラフを構築できます。
あとはこのグラフ上で \((1, N)\) に対応する頂点を始点とした幅優先探索を行い、偶数長奇数長の回文をそれぞれ調べればよいです。(偶数長は全ての頂点 \(i\) について \((i, i)\) に対応する頂点への最短距離、奇数長は、全ての辺 \((a, b)\) について、\((a, b)\) に対応する頂点と \((b, a)\) に対応する頂点への最短距離を見ればよいです)