//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
vector<int> G[100100];
int fa[100100],siz[100100];
inline int anc(int x)
{
	while(fa[x]!=x) x=fa[x]=fa[fa[x]];
	return x;
}
int n,m;
int color[100100];
bool dfs(int u,int c)
{
	color[u]=c;
	for(auto v:G[u])
		if(~color[v])
		{
			if(color[v]==c)
				return true;
		}
		else if(dfs(v,c^1))
			return true;
	return false;
}
int depth[100100],f[100100];
bool used[100100];
bool vis[100100];
void dfs2(int u,int fa)
{
	vis[u]=1;
	f[u]=fa;
	depth[u]=depth[fa]+1;
	for(auto v:G[u])
		if(v!=fa&&!vis[v])
			dfs2(v,u);
}
bool checkEven()
{
	memset(depth,0,sizeof(depth));
	memset(used,0,sizeof(used));
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
		if(!depth[i])
			dfs2(i,0);
	for(int i=1;i<=n;i++)
		for(auto j:G[i])
			if(depth[i]+1<depth[j])
			{
				if((depth[j]^depth[i])&1)
					return true;
				int tmp=j;
				while(tmp!=i)
				{
					if(used[tmp]) return true;
					used[tmp]=1;
					tmp=f[tmp];
				}
			}
	return false;
}
bool checkOdd()
{
	memset(color,-1,sizeof(color));
	for(int i=1;i<=n;i++)
		if(color[i]==-1)
			if(dfs(i,0))
				return true;
	return false;
}
bool checkOdd2()
{
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
		siz[i]=1;
	}
	for(int i=1;i<=n;i++)
		for(auto j:G[i])
		{
			int u=anc(i),v=anc(j);
			if(u!=v)
			{
				fa[u]=v;
				siz[v]+=siz[u];
			}
		}
	memset(color,-1,sizeof(color));
	for(int i=1;i<=n;i++)
		if(fa[i]==i&&siz[i]>3)
			if(dfs(i,0))
				return true;
	return false;
}
bool check2step()
{
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
		siz[i]=0;
	}
	for(int i=1;i<=n;i++)
		for(auto j:G[i])
		{
			int u=anc(i),v=anc(j);
			if(u!=v)
			{
				fa[u]=v;
				siz[v]+=siz[u]+1;
			}
		}
	for(int i=1;i<=n;i++)
		if(fa[i]==i)
			if(siz[i]>=3)
				return true;
	return false;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].pb(v);
		G[v].pb(u);
	}
	if(n==3) die("-1");
	if(!m) die("5");
	if(m==1) die("4");
	if(checkEven()&&checkOdd()) die("0");
	if(checkEven()) die("1");
	if(checkOdd2()) die("1");
	if(check2step()) die("2");
	die("3");
	return 0;
}