ABC197 F - Construct a Palindrome (600)
キューに$ (始点、終点、長さ)の組み合わせを登録してBFSする
キューから順に取り出して以下を行う
既に長さが短い場合は飛ばす
多分存在しない
最小値が既に現在の長さ以下なら飛ばす
始点と終点が一緒なら最小値を更新
始点と終点が隣なら最小値を更新
始点と終点の辺のペアを見て両方同じ文字の辺なら移動可能なのでキューに追加する
既にそのペアでより小さい値で見ていた場合は飛ばす
見る辺の組み合わせは$ O(M^2)、隣接行列等の構築が$ O(N^2)で全体で$ O(N^2+M^2)