分类讨论+点双存边+判奇偶环，但是厌氧了是为什么，好像是点双存边出问题了，但是关掉O2是没事的

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define mk(u, v) make_pair(u, v)
#define pii pair<int, int>
#define ub upper_bound
#define lb lower_bound
const int N = 2e6 + 10;
const int inf = 0x7FFFFFFF;
const ll INF = 0x7FFFFFFFFFFFFFFF;
int top[N];
int dep[N];
int sz[N];
vector<int>G[N];
vector<int>T[N];
int n, m;
int find(int x){
	if(top[x] == x)
		return x;
	return top[x] = find(top[x]);
}
void merge(int u, int v){
	u = find(u);
	v = find(v);
	if(u == v)
		return;
	if(dep[u] < dep[v])
		swap(u, v);
	top[v] = u;
	sz[u] += sz[v];
	if(dep[v] == dep[u])
		dep[u]++;
}
void pre(int u){
	for(auto v : G[u])
		if(find(u) != find(v)){
			merge(u, v);
			pre(v);
		}
}
int dfn[N], low[N], dtt;
int stk[N], stt;
pii stke[N];
int ett;
vector<int>scc[N];
int ctt;
int col[N];
int Col[N];
vector<pii>e[N];
void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++dtt;
	stk[++stt] = u;
	for (auto v : G[u]) {
		if (!dfn[v]) {
			stke[++ett] = mk(u, v);
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]) {
				ctt++;
				while(stk[stt] != v)
					scc[ctt].emplace_back(stk[stt--]);
				scc[ctt].emplace_back(stk[stt--]);
				scc[ctt].emplace_back(u);
				while(stke[ett] != mk(u, v))
					e[ctt].emplace_back(stke[ett--]);
				e[ctt].emplace_back(stke[ett--]);
			}
		}
		else{
			stke[++ett] = mk(u, v);
			if(v != fa)stke[++ett] = mk(v, u);
			low[u] = min(low[u], dfn[v]);
		} 
	}
}
bool d[2][N];
int root;
void dfs(int u, int fa, int o){
	for(auto v : T[u]){
		if(v == fa)
			continue;
		if(!d[o ^ 1][v]){
			d[o ^ 1][v] = 1;
			if(v == root)
				continue;
			dfs(v, u, o ^ 1);
		}
	}
}
int lenmax = 0;
int vis[N];
int vtt;
void dfs2(int u, int dis){
	if(vis[u] == vtt)
		return;
	vis[u] = vtt;
	for(auto v : G[u])
		dfs2(v, dis + 1);
	if(dis > lenmax){
		lenmax = dis;
		root = u;
	}
}
signed main(){
	freopen("graph.in", "r", stdin);
	freopen("graph.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	srand(time(0));
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	if(n < 4){
		cout << -1;
		return 0;
	}
	for(int i = 1; i <= n; i++)
		top[i] = i, dep[i] = sz[i] = 1;
	for(int i = 1; i <= n; i++)
		if(find(i) == i)pre(i); 
	for(int i = 1; i <= n; i++)
		if(!dfn[i]){
			stt = 0;
			ett = 0;
			tarjan(i, 0);
		}
	int ans = 5;
	int ans1 = 5, ans2 = 5;
	for(int i = 1; i <= ctt; i++){
		for(auto u : scc[i])
			col[u] = i, T[u].clear(), d[0][u] = d[1][u] = 0;
		for(auto t : e[i])
			T[t.first].push_back(t.second);
		root = scc[i][0];
		dfs(root, 0, 0);
		for(auto u : scc[i]){
			if(T[u].size() > 2)
				d[0][root] = 1;
		}
		if(d[0][root] && d[1][root])
			ans = min(ans, 0);
		else if(d[0][root])
			ans = min(ans, 1), ans1 = min(ans1, 0);
		else if(d[1][root] && sz[find(root)] >= 4)
			ans = min(ans, 1), ans2 = min(ans2, 0);
		else if(d[1][root])
			ans = min(ans, 2), ans2 = min(ans2, 0);
		else if(sz[find(root)] >= 4)
			ans = min(ans, 2), ans1 = min(ans1, 2), ans2 = min(ans2, 1);
		else if(sz[find(root)] >= 3)
			ans = min(ans, 3), ans1 = min(ans1, 2), ans2 = min(ans2, 1);
		else if(sz[find(root)] >= 2)
			ans = min(ans, 4);
	}
	for(int i = 1; i <= n; i++)
		if(find(i) == i){
			root = i;
			vtt++;
			lenmax = 0;
			dfs2(root, 1);
			vtt++;
			lenmax = 0;
			dfs2(root, 1);
			if(lenmax >= 4)
				ans1 = min(ans1, 1);
		}
	int cnt = 0;
	for(int i = 1; i <= n; i++)
		if(i == find(i) && sz[i] >= 2)cnt++;
	if(cnt >= 2)ans = min(ans, 3);
	ans = min(ans, ans1 + ans2);
	cout << ans;
	return 0;
}

数据生成器

#include<bits/stdc++.h>
#include<ctime>
#include<random>
#define ll long long
#define lll __int128
#define ull unsigned long long
#define veci vector<int>
#define vecl vector<long long>
using namespace std;
default_random_engine e;
long long random(long long l, long long r) {
	uniform_int_distribution<long long>u(l, r);
	return u(e);
}
int main(){
	freopen("date.in","w",stdout);
	e.seed(time(0));
    int n = 500000, m = 1000000;
    cout << n <<' '<<m<< '\n';
    for(int i = 1; i <= m; i++){
    	cout << random(1, n) << ' ' << random(1, n) << '\n';
	}
	return 0;
}