次のグラフ \(G\) を作ります：

• 作るべき分銅全体を頂点集合とする．
• 同時に作ることができる 2 つの分銅に 2 つ辺を張る．

なお，このグラフは，自己ループを含むことがあります．

問題は次のようになります：

• 最小個数の辺を選んで，どの頂点も 2 回以上選ばれているようにせよ．

2 回よりたくさん選ぶことを見なかったことにすることで，これは次のように言い換えられます．

• タイプ A の辺：両端点を選ぶ．
• タイプ B の辺：片方の端点を選ぶ．
• これら 2 種で，どの頂点もちょうど 2 回選ばれているようにして，合計個数を最小化せよ．

これは容易に次に帰着できます．

• タイプ A の辺を選んで，どの頂点も 2 回以下選ばれているようにするとき，その個数を最大化せよ．

あるいは次のように言い換えてもよいです．

• グラフ \(G\) の部分グラフであって，どの連結成分もパス・サイクルのどちらかであるものを選ぶとき，その辺の個数の最大化せよ．

パス・サイクルには，すべての点の入次数・出次数が \(1\) 以下であるような向き付けが存在します．逆に，すべての点の入次数・出次数が \(1\) 以下であるような有向グラフの連結成分は無向グラフとしてパス・サイクルのどちらかです．

よって，\(G\) の辺を双方向の有向辺に取り換えることで，次の問題になります：

• \(G\) は有向グラフである．このうち最大個数の辺を選んで，どの頂点の出次数・入次数も \(1\) 以下であるようにせよ．

\(v\) の出次数・入次数を使用することを表す頂点を考えることで，二部マッチングの形になります．より詳しくは，次のグラフの最大マッチングを考えることになります：

• \(G\) の各頂点 \(v\) に対して，\(v_{\mathrm{in}}, v_{\mathrm{out}}\) という 2 つの頂点を作る．
• \(G\) の各辺 \(uv\) に対して \(u_{\mathrm{out}}\) と \(v_{\mathrm{in}}\) を結ぶ．

解答例：https://atcoder.jp/contests/arc013/submissions/42113368