C++(g++ 7.5.0) 解法, 执行用时: 135ms, 内存消耗: 36056K, 提交时间: 2022-10-04 15:18:55

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl '\n'
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;

int n,m;
vector<int>g[maxn];

int dfn[maxn],dep[maxn],tag[maxn],tim,has_odd,has_even;
int max_odd;

void dfs(int x,int fa){
	dfn[x]=++tim;
	for(auto v:g[x]){
		if(v!=fa){
			if(!dfn[v]){
				dep[v]=dep[x]+1;
				dfs(v,x);
				tag[x]+=tag[v];
			}else if(dfn[v]<dfn[x]){
				if((dep[x]-dep[v])%2)has_even=1;
				else{
					has_odd=1;
					max_odd=max(dep[x]-dep[v]+1,max_odd);
				}
				tag[x]++;
				tag[v]--;
			}
		}
	}
	if(tag[x]>1)has_even=1;
}

int check(){
	for(int i=1;i<=n;i++){
		for(auto x:g[i]){
			if(g[i].size()>2&&g[x].size()>2)return 1;
			for(auto j:g[i]){
				if(j==x)continue;
				for(auto y:g[x]){
					if(y==i)continue;
					if(j!=y)return 1;
				}
			}
		}
	}
	return 0;
}

int main(){

    IOS

    cin>>n>>m;

	if(n<4){
		cout<<-1<<endl;
		return 0;
	}

	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}

	for(int i=1;i<=n;i++){
		if(!dfn[i])dfs(i,-1);
	}

	if(has_even&&has_odd)cout<<0<<endl;
	else if(has_even)cout<<1<<endl;
	else if(has_odd){
		if(max_odd>3||check())cout<<1<<endl;
		else cout<<2<<endl;
	}else {
		int ans=5-min(2,m);
		for(int i=1;i<=n;i++)if(g[i].size()>2)ans=2;
		for(int i=1;i<=n;i++){
			for(auto j:g[i]){
				if(g[i].size()>1&&g[j].size()>1)ans=2;
			}
		}
		cout<<ans<<endl;
	}

}