まず、\(a, b, c, d\) の偶奇が一致していないものの答えは \(0\) です。

それぞれの辺についての時計回りに通る回数と反時計回りに通る回数の差は等しいです。

よって、\(1\) つの辺について、時計回りに通る回数を決めると、全ての辺について、時計回りに通る回数と反時計回りに通る回数が決まります。

ある辺の時計回りに通る回数を決め打つと、有向グラフのオイラー路の数え上げになります。これは BEST Theorem を用いて、\(O(|頂点数|^{3})\) で求めることができます。

BEST Theorem については ABC の過去問の解説に詳しく書かれています。

実装例 c++ 503 ms