\(B=N-A\) とします．

準備段階では B の頂点に駒を置き，実際のプレイでは A,B,A,… と交互に移動させていって，移動できないほうが負け，としてよいです．

まずグラフの形と各頂点の A,B が決まっている場合の勝敗を考えます． これは有名問題です． B 頂点と A 頂点のマッチングを考えて，B 頂点を全部使うようなマッチングがあるなら Alice の勝ち，そうでないなら Bob の勝ちです．

つまり，Bob の目標は，マッチングが存在しないようにすることです．

ホールの定理を用いると，次の条件を満たす頂点集合 \(s\) が取れれば良いことがわかります．

• \(1 \leq |s| \leq B\)
• \(s\) 内の頂点は全部 B
• \(s\) のいずれかの頂点と隣接する A 側頂点の個数は \(|s|-1\) 以下

ここで，\(s\) を固定してみると，B 側にある \(s\) 以外の頂点は \(s\) と隣接するもので埋めていって損しないとわかります．

そして，頂点にラベルをつけない状態で \(s\) が満たすべき条件を整理すると，以下のように言い換えることができます．

• \(1 \leq |s| \leq B\)
• \(s\) のいずれかの頂点と隣接する \(s\) 以外の頂点数は \(B-1\) 以下

ここまでわかれば，\(s\) の候補を全探索し，隣接頂点数を \(B-1\) 以下にするためのコストを計算すれば，元の問題を解くことができます．

計算量は \(O(2^N N^2)\) です．

回答例(C++)