#include<bits/stdc++.h>
#define pd push_back
#define all(A) A.begin(),A.end()
#define lower_bound lb
#define ve std::vector
typedef long long ll;
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
typedef long double LD;
bool FileIfstream(std::string name){
	std::ifstream f(name.c_str());
	return f.good();
}
namespace Math{
	ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
	ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
const int N=2e5+10;
const int mod=998244353;
int n,m;
struct none{
	ve<ve<int>>v;
	ve<bool>vis;
	void init(ve<ve<int>>&rv){
		v=rv;vis.assign(n+1,false);
	}
	bool dfs(int x,int F){
		vis[x]=true;
		for(auto y:v[x]){
			if(y^F){
				if(vis[y])return true;
				if(dfs(y,x))
					return true;
			}
		}
			
		return false;
	}
	bool work(){
		for(int i=1;i<=n;i++)
			if(!vis[i]){
				if(dfs(i,0))
					return true;
			}
		return false;
	}
	bool dfs2(int x,int dep){
		if(dep==4)return true;
		vis[x]=true;
		for(auto y:v[x]){
			if(!vis[y]){
				if(dfs2(y,dep+1))
					return true;
			}
		}
		vis[x]=false;
		return false;
	}
	bool find_list(){
		vis.assign(n+1,false);
		for(int i=1;i<=n;i++)
			if(dfs2(i,1))
				return true;
		return false;
	}
}E1;
struct odd{
	ve<ve<int>>v;
	ve<int>col;
	void init(ve<ve<int>>&rv){
		v=rv;col.assign(n+1,-1);
	}
	bool dfs(int x,int c){
		col[x]=c;
		for(auto y:v[x])
			if(col[y]==-1){
				if(dfs(y,c^1))
					return true;
			}else if(col[y]^col[x]^1)return true;
		return false;
	}
	bool work(){
		for(int i=1;i<=n;i++)
			if(col[i]==-1){
				if(dfs(i,0))
					return true;
			}
		return false;
	} 
}E2;
struct even{
	std::map<std::pair<int,int>,int>mp1,mp2;
	ve<ve<int>>v;
	ve<int>dep;
	ve<bool>cov;
	ve<int>f;
	void init(ve<ve<int>>&rv){
		v=rv;dep.assign(n+1,0);
		cov.assign(n+1,false);
		f.assign(n+1,0);
	}
	void dfs(int x,int F){
		dep[x]=dep[F]+1;f[x]=F;
		for(auto y:v[x])
			if(y!=F&&!dep[y])
				mp1[{x,y}]=mp1[{y,x}]=1,dfs(y,x);
	}
	bool work(){
		for(int i=1;i<=n;i++)
			if(!dep[i])dfs(i,0);
		for(int i=1;i<=n;i++)
			for(auto p:v[i])
				if(dep[p]<dep[i]&&mp1[{i,p}]!=1){
					int x=i,y=p;
					if(dep[x]<dep[y])std::swap(x,y);
					if((dep[x]-dep[y])&1)
						return true;
					while(x^y){
						if(mp2[{x,f[x]}]==1)
							return true;
						mp2[{x,f[x]}]=1;
						x=f[x];
					}
				}
		return false;
	}
}E3;
void solve(){
	//don't forget to open long long
	std::cin>>n>>m;
	if(n<=3)return std::cout<<"-1\n",void();
	if(m<=2)return std::cout<<5-m<<'\n',void(); 
	ve<ve<int>>v(n+1);
	for(int i=1;i<=m;i++){
		int x,y;std::cin>>x>>y;
		v[x].pd(y);v[y].pd(x);
	}
	E1.init(v);
	E2.init(v);
	E3.init(v);
	bool f1=E1.work(),f2=E2.work(),f3=E3.work();
	if(!f1){
		if(E1.find_list())
			return std::cout<<2<<'\n',void();
		else std::cout<<3<<'\n',void();
	}else if(f2&&f3)return std::cout<<0<<'\n',void();
	else if(f2){
		if(E1.find_list())
			return std::cout<<1<<'\n',void();
		else std::cout<<2<<'\n',void();
	}else{
		std::cout<<1<<'\n',void();
		return; 
	}
}
int main(){
#ifndef ONLINE_JUDGE
	if(!FileIfstream("IO.in")){
		freopen("IO.in","w",stdout);
		return 0;
	}
	freopen("IO.in","r",stdin);
	freopen("IO.out","w",stdout);
#endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int T=1;
	//std::cin>>T;
	while(T--)solve();

	return 0;
}