#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
const ll N=2e5+9;
ll n,m,dep[N],vis[N],fa[N];
vector<ll>to[N],es[N],p;
void dfs2(ll x,ll f){
	vis[x]=1,fa[x]=f,dep[x]=dep[f]+1;
	for(ll y:to[x]){
		if(y==f||vis[y])continue;
		es[x].push_back(y);
		es[y].push_back(x);
		dfs2(y,x);
	}
}
void dfs3(ll x,ll f){
	dep[x]=dep[f]+1;
	vis[x]=1;
	p.push_back(x);
	for(ll y:to[x]){
		if(y==f||vis[y])continue;
		dfs3(y,x);
	}
}
bool Med;
int main(){
	cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
	n=read(),m=read();
	if(n<=3)return puts("-1"),0;
	if(m<=2)return write(5-m),0;
	rep(i,1,m){
		ll x=read(),y=read();
		to[x].push_back(y);
		to[y].push_back(x);
	}
	ll fl1=0,fl2=0;
	rep(i,1,n){
		if(!vis[i])dfs2(i,0);
	}
	rep(i,1,n){
		for(ll j:to[i]){
			if(fa[j]==i||fa[i]==j)continue;
			ll d=dep[i]+dep[j];
			if(d&1)fl2=1;
			else fl1=1;
		}
	}
	if(fl1&&fl2)return puts("0"),0;
	if(fl2)return puts("1"),0;
	ll mx=0;
	rep(i,1,n){
		for(ll j:to[i]){
			if(fa[j]==i||fa[i]==j)continue;
			mx=max(mx,dep[i]+dep[j]);
		}
	}
	memset(vis,0,sizeof(vis));
	rep(i,1,n){
		if(!vis[i]){
			p.clear();
			dfs3(i,0);
			ll S=0;
			for(ll x:p){
				if(dep[x]>dep[S])S=x;
				vis[x]=0;
			}
			p.clear();
			dfs3(S,0);
			for(ll x:p)mx=max(mx,dep[x]-1);
		}
	}
	if(mx>=3){
		if(fl1)return puts("1"),0;
		return puts("2"),0;
	}
	if(fl1)return puts("2"),0;
	puts("3");
	return 0;
}