\((1, 2, \dots , N)\) の順列 \(p\) を用いて、以下のように \(N\) 頂点 \(N\) 本のグラフを考えます。

• 頂点 \(p[i]\) と \(i\) を結ぶ

このグラフは次数がすべて \(2\) です。また、任意の「頂点の次数が 2 である単純無向グラフ」に対して、そのようなグラフを生成する \(p\) が \(1\) つ以上存在します。よって、\(p\) を全探索することで、問題を解くことができます。ただし、\(p[i] = i\) もしくは \(p[p[i]] = i\) が成り立つ \(i\) が存在するときは、「頂点の次数が 2 である単純無向グラフ」にならないので除外します。

https://atcoder.jp/contests/abc412/submissions/67165690