Menger’s Theorem より、\(3\) 頂点以上の二重連結成分において、その成分に属する任意の頂点対 \((s, t)\) に対し、\(s, t\) を結ぶ点素なパスが二つ以上存在します。

与えられたグラフを二重連結成分分解します。\(s, t\) を結ぶパスにおいて通る成分の集合は一意であり、それらを \(c_1, \dots, c_n\) とおきます。\(s\) から出発して \(t\) へ到達し、再び \(s\) に戻るような経路において、\(c_k, c_{k + 1}\) の共通部分である頂点は必ず \(2\) 度通らなければならず、また、それ以外の頂点は \(1\) 度しか通らないようにすることができます。

各頂点について、それを \(2\) 度通らなければならないような \((s, t)\) の総数を数えることを考えます。与えられたグラフの Block-cut Tree を構築し、全ての辺 \((a, b)\)（ただし、\(a\) が頂点に、\(b\) が成分に対応するとする）について、以下の値を足し合わせて \(2\) で割ったものが答えになります。

• Block-cut Tree を \(b\) を根として根付き木にしたときの \(a\) を根とする部分木に属する、元のグラフの頂点に対応する頂点の個数を \(x\) として、\((x - 1)(N - x)\)

よって、この問題を \(O(N + M)\) で解くことができました。