这里定义 deg(u) 表示 u 的非自环连边个数。

考虑每次取出度数最大的点，若 deg(u)\le 2 则图由若干链和环构成（这里每个点上可能会挂着一些自环），可以在上面跑 dp，否则容斥：

若 u 任选则这个点连的自环任选，然后对所有的 (u,v)\in E，连一个自环 (v,v)；

若 u 被钦定不选则把这个点的连边都删了。

每次 m 至少减 3，复杂度最坏为 O(2^{m/3}n)，容易通过。

这 140 排版咋这么神经。