#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;
void dfs(int u,int fa=0){
	for(int v:to[u])if(v^fa){
		if(!~col[v])col[v]=!col[u],dfs(v,u);
		else if(col[u]==col[v])t1=1;
		else t2=1;
	}
}
void find(){
	for(int u=1;u<=n;u++){
		for(int v:to[u]){
			if(to[u].size()>1&&to[v].size()>1){
				t3=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);
	find();
	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;
}