#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=1e5+10;
int n,m,col[N];
vector<int>to[N];
int t1,t2,t3;
int fa[N],tag[N],dep[N];
vector<pair<int,int> >E;
void dfs(int u,int fa=0){
	dep[u]=dep[fa]+1;
	for(int v:to[u])if(v^fa){
		if(!~col[v])col[v]=!col[u],dfs(v,u);
		else{
			if(u<v)E.push_back({u,v});
			if(col[u]==col[v])t1=1;
		}
	}
}
int cur[N],rk[N],vis[N];
void find(){
	iota(cur,cur+1+n,0);
	sort(cur+1,cur+1+n,[](int x,int y){
		int tx=to[x].size(),ty=to[y].size();
		return tx^ty?tx<ty:x<y;
	});
	for(int i=1;i<=n;i++)rk[cur[i]]=i;
	for(int u=1;u<=n;u++){
		for(int v:to[u])vis[v]=1;
		for(int v:to[u])if(rk[u]<rk[v]){
			for(int w:to[v])if(w^u){
				if(!vis[w]){
					if(to[w].size()>1||to[u].size()>1){
						t3=1;
					}
				}else{
					if(to[w].size()>2||to[u].size()>2){
						t3=1;
					}
				}
			}
		}
		for(int v:to[u])vis[v]=0;
	}
}
void cover(int u,int t){
	if(dep[u]<dep[t])swap(u,t);
	for(;u^t;u=fa[u]){
		if(tag[u]){
			t2=1;return;
		}
		tag[u]=1;
	}
}
int main(){
	memset(col,-1,sizeof col);
	scanf("%d%d",&n,&m);
	for(int u,v,i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		to[u].push_back(v),to[v].push_back(u);
	}
	if(n<=3)return cout<<-1<<endl,0;
	if(!m)return cout<<5<<endl,0;
	if(m==1)return cout<<4<<endl,0;
	if(m==2)return cout<<3<<endl,0;
	for(int i=1;i<=n;i++)if(!~col[i])col[i]=0,dfs(i);
	for(auto e:E)cover(e.first,e.second);
	find();
	// debug(ary(col,1,n));
	// debug(t1,t2,t3);
	if(t1&&t2)return cout<<0<<endl,0;
	if(t1){
		if(t3)cout<<1<<endl;
		else cout<<2<<endl;
		return 0;
	}
	if(t2)return cout<<1<<endl,0;
	if(t3)return cout<<2<<endl,0;
	cout<<3<<endl;
	return 0;
}