OMC152(C)

点数: 400

Writer: mn_7545

　OMC国は $12$ 個の島からなり，どの相異なる $2$ 個の島についても，ちょうど一本の橋で双方向に結ばれています．おもち君はこれらの橋を，以下の条件をみたすように赤色・緑色・青色のいずれかで塗り分けることにしました：

• どの色 $C$ に対しても，相異なる $2$ 個の島 $I_1,I_2$ が存在し，$C$ で塗られた橋のみを渡ることを繰り返して $I_1$ から $I_2$ に到達できない．

• どの島に対しても，ある他の島が存在し，それらは赤色で塗られた橋で結ばれている．

このような塗り分け方のうち，赤色で塗られた橋の本数が最大値をとるようなものがいくつあるかを求めてください．ただし，すべての島は区別して考えるものとします．