记一个 qiuzx 在 CF 上发的做法。
考虑建出这个图的圆方树，在圆方树上 dp。\(dp_{i,0/1/2}\) 表示以 \(i\) 为根的子树，\(i\) 的覆盖次数（如果 \(i\) 是方点记录的就是 \(fa_i\) 的覆盖次数）。
对于圆点处的 dp 合并是容易的。
对于方点处的合并看起来不是很好做。题目限制经过每个点的环 \(\le 5\) 个，这个限制对于一个点双是很严的。
对于一个点双，首先有每个点的度数 \(\le 3\)，否则就至少有 \(\binom{4}{2}=6\) 个环。
再手玩一下，可以发现度数 \(=3\) 的点也是不多的。似乎可以证明最多只有 \(4\) 个点是满足度数 \(=3\) 的。
注意到如果每个点度数 \(\le 2\) 就非常好做了，而我们最终保留的图中每个点度数也 \(\le 2\)，于是考虑对于每个度数为 \(3\) 的点，我们都删掉一条邻边，这样就满足度数 \(\le 2\) 了。
然后整个点双就只剩若干个环和链了，这个可以直接 dp 一下链覆盖的形态，容易做到线性。
总复杂度是 \(O(3^4n^2)\)，可以精细实现到 \(O(3^4n)\)，但是不必要。
在本题的限制下，如果每个点双 \(\le4\) 个度数 \(=3\) 点成立，那么可以说明 \(m\le \frac{5}{3}n\)。此时取出一棵 dfs 树，然后对于非树边搜是否选择，对树做 dp 应该可以做到 \(O(2^{\frac{2}{3}n}n)\)。
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int> ;
template <typename T> void Chkmin(T &x, T y) { x = min(x, y); }const int inf = 1e9;
const int kN = 65;
const int pw3[] = {1, 3, 9, 27, 81, 243, 729};
int n, m, tot, num, tp;
vector<pii> g[kN];
int dfn[kN], low[kN], fa[kN], stk[kN], dp[kN][3];
vector<int> tr[kN];void Clear() {tot = num = 0;fill(dfn, dfn + kN, 0);fill(g, g + kN, vector<pii> ());fill(tr, tr + kN, vector<int> ());
}void Link(int f, int x) { tr[fa[x] = f].push_back(x); }
void Tarjan(int x) {dfn[x] = low[x] = ++tot;stk[++tp] = x;for(pii k : g[x]) {int to = k.first;if(!dfn[to]) {Tarjan(to);Chkmin(low[x], low[to]);if(low[to] >= dfn[x]) {int id = n + ++num, t;Link(x, id);do Link(id, t = stk[tp--]);while(t != to) ;}}else Chkmin(low[x], dfn[to]);}
}bool ban[kN], vis[kN];
vector<pii> ng[kN];
vector<int> gg[kN];void DFS2(int x, vector<int> &v) {vis[x] = 1;v.push_back(x);for(int to : gg[x]) {if(!vis[to]) DFS2(to, v);}
}int f[kN][3];
int ff[kN][3][3];int F(vector<int> id) {int siz = id.size();for(int i = 0; i < siz; i++) fill(f[i], f[i] + 3, inf);int p = id[0];f[0][0] = min(dp[p][0], dp[p][1]);f[0][2] = min({dp[p][0] + 1, dp[p][1] + 1, dp[p][2]});for(int i = 1; i < siz; i++) {int p = id[i];int *g = f[i - 1];f[i][0] = g[2] + min(dp[p][0], dp[p][1]);f[i][1] = min(g[0], g[1]) + dp[p][0];f[i][2] = min(min({g[0], g[1], g[2]}) + min(dp[p][0], dp[p][1]) + 1, g[2] + dp[p][2]);}return f[siz - 1][2];
}
int G(vector<int> id) {int siz = id.size();for(int i = 0; i < siz; i++) {for(int j : {0, 1, 2}) fill(ff[i][j], ff[i][j] + 3, inf);}ff[0][0][0] = ff[0][1][1] = ff[0][2][2] = 0;for(int i = 1; i < siz; i++) {int p = id[i];for(int j : {0, 1, 2}) {int *f = ff[i][j], *g = ff[i - 1][j];f[0] = g[2] + min(dp[p][0], dp[p][1]);f[1] = min(g[0], g[1]) + dp[p][0];f[2] = min(min({g[0], g[1], g[2]}) + min(dp[p][0], dp[p][1]) + 1, g[2] + dp[p][2]);}}int res = 0;int p = id[0];for(int i : id) res += dp[i][0];int f[3][3];memcpy(f, ff[siz - 1], sizeof(f));Chkmin(res, f[0][2] + min(dp[p][0], dp[p][1]));Chkmin(res, min(f[1][0], f[1][1]) + dp[p][0]);Chkmin(res, min({f[2][0], f[2][1], f[2][2]}) + min(dp[p][0], dp[p][1]) + 1);Chkmin(res, f[2][2] + dp[p][2]);return res;
}int Calc(int all) {fill(vis + 1, vis + n + 1, 0);fill(gg + 1, gg + n + 1, vector<int> ());for(int i = 1; i <= n; i++) {if(!((all >> i) & 1)) continue;for(pii k : ng[i]) {int to, id;tie(to, id) = k;if(((all >> to) & 1) && !ban[id]) gg[i].push_back(to);}}int res = 0;for(int i = 1; i <= n; i++) {if(!((all >> i) & 1) || vis[i]) continue;if(gg[i].size() <= 1) {vector<int> node;DFS2(i, node);res += F(node);}}for(int i = 1; i <= n; i++) {if(!((all >> i) & 1) || vis[i]) continue;vector<int> node;DFS2(i, node);res += G(node);}return res;
}int p3[kN], deg[kN];void DP(int rt, int *f, int all) {fill(deg + 1, deg + n + 1, 0);fill(ng + 1, ng + n + 1, vector<pii> ());for(int i = 1; i <= n; i++) {if(!((all >> i) & 1)) continue;for(pii k : g[i]) {int to = k.first;if((all >> to) & 1) ng[i].push_back(k);}}int c3 = 0;for(int i = 1; i <= n; i++) {if(ng[i].size() == 3) p3[++c3] = i;}for(int i = 0; i < pw3[c3 + 1]; i += 3) {fill(ban + 1, ban + m + 1, 0);for(int j = 1; j <= c3; j++) {int w = i / pw3[j] % 3;ban[ng[p3[j]][w].second] = 1;}dp[rt][2] = 0, dp[rt][0] = dp[rt][1] = inf;Chkmin(f[0], Calc(all));dp[rt][1] = 0, dp[rt][0] = dp[rt][2] = inf;Chkmin(f[1], Calc(all) - 1);dp[rt][0] = 0, dp[rt][1] = dp[rt][2] = inf;Chkmin(f[2], Calc(all));}
}void DFS(int x) {for(int to : tr[x]) DFS(to);if(x <= n) {int old[3];dp[x][0] = dp[x][1] = 0, dp[x][2] = 1;for(int to : tr[x]) {memcpy(old, dp[x], sizeof(old));int *f = old, *g = dp[to];dp[x][0] = f[0] + g[0];dp[x][1] = min(f[0] + g[1], f[1] + g[0]);dp[x][2] = min({f[1] + g[1] + 1, f[0] + g[2], f[2] + g[0]});}}else {dp[x][0] = dp[x][1] = dp[x][2] = inf;int all = (1 << fa[x]);for(int to : tr[x]) all |= (1 << to);DP(fa[x], dp[x], all);}Chkmin(dp[x][1], dp[x][0]);Chkmin(dp[x][2], dp[x][1] + 1);
}void Solve() {Clear();cin >> n >> m;for(int i = 1; i <= m; i++) {int u, v;cin >> u >> v;g[u].emplace_back(v, i);g[v].emplace_back(u, i);}Tarjan(1);DFS(1);cout << n - dp[1][2] << "\n";
}int main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);ios::sync_with_stdio(0), cin.tie(0);int t;cin >> t;while(t--) Solve();return 0;
}