各頂点の次数から \(1\) を引いた値の列を \(d_1,d_2,\cdots,d_N\) とおきます．

各 \(0 \leq s \leq N-2\) について，総和が \(s\) になる \(d_i\) の部分集合のサイズの最小値を \(m(s)\)，最大値を \(M(s)\) とおきます．（そのような部分集合がない場合は，便宜的に \(m(s)=\infty,M(s)=-\infty\) とします） このとき，以下の性質が成り立ちます．

• すべての \(m(s) \leq c \leq M(s)\) について，ちょうど \(c\) 個の要素を \(d\) から選び，その総和を \(s\) にすることができる．

この性質を認めてしまえば，この問題は簡単に解けます． \(m(s)\) を DP で求めることを考えます． \(d\) に登場する値は高々 \(O(\sqrt{N})\) 通りであるため，値で分類を行い，各値についてスライド最小値を使って遷移を高速化すれば，\(m(s)\) は \(O(N \sqrt{N})\) で求めることができます． \(M(s)\) は \(m(s)\) の値からすぐにわかります． よって，この問題は \(O(N \sqrt {N})\) で解けます．

最後に，上で仮定した性質を証明します．

\(d\) に含まれる \(0\) の個数を \(z\) とおきます． \(M(s)-m(s) \leq 2z\) を示せばよいです．これは，\(M(s)\) を達成する解では必ず \(z\) 個の \(0\) が使用されており，逆に \(m(s)\) を達成する解では一つも \(0\) が使用されていないためです．

ところで，\(d\) の任意の部分集合 \(x\) について，そのサイズ \(c\) と総和 \(s\) に関して，\(-z \leq s-c \leq z-2\) が成立します． なぜなら，\(d_i-1<0\) となる \(d_i-1\) の総和が \(-z\) であり，また \(d_i-1>0\) となる \(d_i -1\) の総和が \(z-2\) だからです． このとき，\(-z \leq s-M(s) \leq s-m(s) \leq z-2\) より，\(M(s)-m(s) \leq 2z\) が従います． よって示されました．