#include<bits/stdc++.h>
using namespace std;
#define pr pair<int,int>
#define fi first
#define se second
int const MAX=1e5+10;
vector<int> V[MAX];
bool ji,ou;
int dep[MAX],fa[MAX];
bool fl[MAX];
set<pr> S;
void maketag(int now,int top){
	//cerr<<now<<" "<<top<<"\n";
	if(now==top)return ;
	if(S.count({now,fa[now]})){
		//cerr<<now<<" "<<top<<"\n";
		ou=true;
		return ;
	}
	S.insert({now,fa[now]});
	maketag(fa[now],top);
}
void dfs(int t1,int last){
	if(fl[t1]){
		int tp=dep[last]-dep[t1];
		if(tp<=0||tp==1)return;
		if(tp%2==1)ou=true;
		if(tp%2==0){
			ji=true;
			maketag(last,t1);
		}
		return;
	}
	fa[t1]=last;
	dep[t1]=dep[last]+1;
	fl[t1]=true;
	for(auto it:V[t1]){
		dfs(it,t1);
	}
	return;
}
int maxx=0;
void dfs2(int now,int last){
	maxx=max(maxx,dep[now]);
	if(fl[now])return;
	fl[now]=true;
	for(auto it:V[now]){
		//dep[it]=max(dep[it],dep[now]+1);
		if(fl[it])continue;
		dep[it]=dep[now]+1;
		dfs2(it,now);
	}
	return;
}
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		V[u].push_back(v);
		V[v].push_back(u);
	}
	if(n<=3){
		cout<<-1;
		return 0;
	}
	if(m<=2){
		cout<<5-m;
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(!fl[i])dfs(i,0);
	}
	//cerr<<ji<<" "<<ou<<"\n";
	if(ji&&ou){
		cout<<0;
		return 0;
	}
	bool qwq=false;
	for(int i=1;i<=n;i++){
		bitset<MAX> B;
		for(auto it:V[i])B[it]=1;
		for(auto it:V[i]){
			bitset<MAX> B2;
			for(auto it2:V[it])B2[it2]=1;
			bitset<MAX> B3=B2|B;
			//if(i==1&&it==2)cerr<<B.count()<<" "<<B2.count()<<" "<<B3.count()<<"\n";
			if(B.count()>=2&&B2.count()>=2&&B3.count()>=4)qwq=true;
			if(qwq)break;
		}
		if(qwq)break;
	}
	if(ji){
		//cerr<<maxx<<"\n";
		if(qwq)cout<<1;
		else cout<<2;
		return 0;
	}
	if(ou){
		cout<<1;
		return 0;
	}
	if(qwq)cout<<2;
	else cout<<3;
	return 0;
}