\(N\) 頂点のグラフ \(H\) を次のように構成します．

• 整数 \(x,y\) が書き込まれている \(G\) の頂点を結ぶ辺であって，頂点を共有しないものが \(2\) つ存在するならば，\(H\) の頂点 \(x,y\) を辺で結ぶ

\(H\) を用いて，回文パスの存在条件を述べます．

偶数長の回文パスの存在条件

偶数長の回文パス \(x \to \dots \to y \to y \to \dots \to x\) が存在する条件は，以下の \(2\) つが成り立つことです．

• \(H\) において，\(x\) から \(y\) へのパスが存在する．
• \(G\) において，\(y\) が書き込まれている \(2\) 頂点（頂点 \(2y-1,2y\)）の間に辺が存在する．

よって，\(2\) つ目の条件を満たす \(y\) について，\(H\) で \(y\) と同じ連結成分に属するすべての \(x\) について，\(x\) から始まる回文パスが存在します．

奇数長の回文パスの存在条件

奇数長の回文パス \(x \to \dots \to y \to z \to y \to \dots \to x\) が存在する条件は，以下の \(2\) つが成り立つことです．

• \(H\) において，頂点 \(x\) から頂点 \(y\) へのパスであって，頂点 \(z\) を通らないものが存在する．
• \(G\) において，\(y\) が書き込まれている \(2\) 頂点（頂点 \(2y-1,2y\)）と，\(z\) が書き込まれているある \(1\) 頂点（頂点 \(2z-1,2z\) のいずれか）の間に辺が存在する．

\(2\) つ目の条件を満たす \(y,z\) が与えられたとき，始点 \(x\) としてあり得るものを考えます．

まず，\(H\) において，\(y,z\) が異なる連結成分に属している場合は，\(y\) と同じ連結成分に属するすべての \(x\) が始点となりえます．

次に，\(H\) において \(y,z\) が同じ連結成分に属している場合を考えます．

• \(z\) が \(H\) の関節点でないとき：\(y\) と \(H\) で同じ連結成分に属するすべての \(x \neq z\) が始点となりえます．
• \(z\) が \(H\) の関節点であるとき：\(H\) から \(z\) を取り除いたあと，\(y\) と同じ連結成分に属するすべての \(x\) が始点となりえます．そのような \(x\) は，\(H\) の block cut tree \(T\)（実際は，\(H\) は非連結でありえるので，森）において部分木をなします．

\(z\) が \(H\) の関節点であるとき以外の条件はすべて \(O(N+M)\) 時間で容易に判定できます．\(z\) が \(H\) の関節点である場合の条件は，\(T\) 上の Euler ツアーと累積和を用いて，すべての \(y,z\) について並列で判定することができます．これも時間計算量は \(O(N+M)\) です．