$N$個の都市と都市$A_i$,$B_i$を結ぶ$M$本の道がある。条件「同じ州に属すどの2つの都市も直接道で結ばれている」を満たすように都市を2つの州に分けたい。これが可能であるかを判定せよ。可能である時、同じ州に属している都市の間にある道の本数の最小値を求めよ。都市と道をグラフとみなし、2つの州に分けることを2色に塗り分けることとする。この時、条件は「同じ色の頂点間には辺がある」と言い換えられる。これを満たすように頂点を色分けするには、間に辺がない2つの頂点は別の色で塗れば良い。補グラフで考えると、辺で結ばれている頂点は別の色で塗るということになる。これが可能であるのは補グラフが二部グラフである時に限るから、条件を満たす色分けが存在するかを判定することができる。色分けが可能である時、同じ色で塗られた頂点間にある辺の本数を最小化したい。\frac{(N-i)(N-i-1)}{2}$である。後は$i$としてありうるものが列挙できれば、答えを求めることができる。補グラフが二部グラフである時、色の塗り分け方は連結成分ごとに$2$通りある。y_C$)のいずれかとなる。x_C$からいくつか選んで足し合わせたものになる。これはDPで容易に求めることができる。計算量は$O(N^2)$であり、十分高速である。0;}解法まとめ補グラフが二部グラフでなければ答えは$-1$(不可能)である。x_C$からいくつか選んで足した値としてありうるものをDPで求める。\frac{(N-i)(N-i-1)}{2}$の最小値である。