//Crimson flames tied through my ears
//Rollin' high and mighty traps
//Pounced with fire on flaming roads
//Using ideas as my maps
//"We'll meet on edges, soon," said I
//Proud 'neath heated brow
//Ah, but I was so much older then
//I'm younger than that now.
//
//Half-cracked prejudice leaped forth
//"Rip down all hate," I screamed
//Lies that life is black and white
//Spoke from my skull, I dreamed
//Romantic facts of musketeers
//Foundationed deep, somehow
//Ah, but I was so much older then
//I'm younger than that now.
//
//Girls' faces formed the forward path
//From phony jealousy
//To memorizing politics
//Of ancient history
//Flung down by corpse evangelists
//Unthought of, thought, somehow
//Ah, but I was so much older then
//I'm younger than that now.
//A self-ordained professor's tongue
//Too serious to fool
//Spouted out that liberty
//Is just equality in school
//"Equality," I spoke the word
//As if a wedding vow
//Ah, but I was so much older then
//I'm younger than that now.
//
//In a soldier's stance, I aimed my hand
//At the mongrel dogs who teach
//Fearing not that I'd become my enemy
//In the instant that I preach
//My existence led by confusion boats
//Mutiny from stern to bow
//Ah, but I was so much older then
//I'm younger than that now.
//
//Yes, my guard stood hard when abstract threats
//Too noble to neglect
//Deceived me into thinking
//I had something to protect
//Good and bad, I define these terms
//Quite clear, no doubt, somehow
//Ah, but I was so much older then
//I'm younger than that now.

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
/*=====================================================================*/
#define ll long long
//#define int ll
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pdd pair<double,double>
#define ull unsigned long long
#define pb push_back
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(s) (s).begin(),(s).end()
#define repd(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define forr(i,a,b,c) for(int i=(int)(a);i<=(int)(b);i+=(int)(c))
#define forn(i,p,n) for(int i=(int)(p);i<=(int)(n);++i)
#define ford(i,p,n) for(int i=(int)(n);i>=(int)(p);--i)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();++i)
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define modcg(x) if(x>=mod)x-=mod;
#define modcl(x) if(x<0)x+=mod;
#define lowbit(x) ((x)&(-(x)))
#define ckmax(x,y) x=max(x,y)
#define ckmin(x,y) x=min(x,y)
/*=====================================================================*/
mt19937 GeN(chrono::system_clock::now().time_since_epoch().count());
int Rand(int l,int r)
{
	uniform_int_distribution<>RAND1(l,r);
	return RAND1(GeN);
}
struct Fastmod
{
	int mod,b;
	typedef __int128 lll;
	void init(int m)
	{
		mod=m;
		b=((lll)1<<64)/mod;
	}
	int operator()(ull a)
	{
		int q=((lll)a*b)>>64,r=a-q*mod;
		modcg(r);
		return r;
	}
}MOD;
int mul(int a,int b)
{
	return MOD(a*b);
}
/*======================================================================*/
//think twice,code once
//think once,debug forever
const int MAXN=1e5+10;
vi v[MAXN];
int n,m;
namespace SUB5
{
	bool check5()
	{
		return m==0;
	}
};
namespace SUB4
{
	bool check4()
	{
		return m==1;
	}
};
namespace SUB0
{
	bool f0=0,f1=0;
	int use[MAXN],col[MAXN],cnt[2][MAXN],vis[MAXN],ins[MAXN],f[MAXN];
	void dfs(int now,int fa)
	{
//		if(fa)
//		{
//			cout<<now<<" "<<fa<<endl;
//		}
		use[now]=1;ins[now]=1;
		for(int u:v[now])
		{
			if(u==fa)
			{
				continue;
			}
			if(!use[u])
			{
				col[u]=col[now]^1;
				f[u]=now;
				dfs(u,now);
			}
			else
			{
				if(ins[u])
				{
					cnt[col[now]][now]++;cnt[col[u]][u]--;
				}
				if(col[u]==col[now])
				{
					f0=1;
				}
				else
				{
					f1=1;
				}
			}
		}
		ins[now]=0;
	}
	void dfs1(int now,int fa)
	{
		vis[now]=1;
		for(int u:v[now])
		{
			if(u==fa)
			{
				continue;
			}
			if(!vis[u])
			{
				dfs1(u,now);
				cnt[0][now]+=cnt[0][u];
				cnt[1][now]+=cnt[1][u];
			}
		}
	}
	bool check0()
	{
		forn(i,1,n)
		{
			if(!use[i])
			{
				dfs(i,0);
				dfs1(i,0);
			}
		}
		if(f0&&f1)
		{
			return 1;
		}
		forn(i,1,n)
		{
//			if(cnt[i])
//			{
//				cout<<i<<" "<<cnt[i]<<endl;
//			}
			if(cnt[0][i]&&cnt[1][i])
			{
				return 1;
			}
		}
		return 0;
	}
};
namespace SUB1
{
	bool f0=0,f1=0;
	int use[MAXN],col[MAXN];
	vi s[2];
	void dfs(int now,int fa)
	{
		s[col[now]].pb(now);
		use[now]=1;
		for(int u:v[now])
		{
			if(u==fa)
			{
				continue;
			}
			if(!use[u])
			{
				col[u]=col[now]^1;
				dfs(u,now);
			}
			else
			{
				if(col[u]==col[now])
				{
					f0=1;
				}
				else
				{
					f1=1;
				}
			}
		}
	}
	bool g0=0,g1=0;
	bool check1()
	{
		forn(i,1,n)
		{
			if(!use[i])
			{
				s[0].clear();s[1].clear();
				dfs(i,0);
				if(!g0)
				{
					for(int u:s[0])
					{
						int cnt=0;
						for(int x:v[u])
						{
							cnt+=col[x]==0;	
						}
						if(cnt!=s[0].size()-1)
						{
							g0=1;
							break;
						}
					}
					for(int u:s[1])
					{
						int cnt=0;
						for(int x:v[u])
						{
							cnt+=col[x]==1;	
						}
						if(cnt!=s[1].size()-1)
						{
							g0=1;
							break;
						}
					}
				}
				if(!g1)
				{
					for(int u:s[0])
					{
						int cnt=0;
						for(int x:v[u])
						{
							cnt+=col[x]==1;	
						}
						if(cnt!=s[1].size())
						{
							g1=1;
							break;
						}
					}
					for(int u:s[1])
					{
						int cnt=0;
						for(int x:v[u])
						{
							cnt+=col[x]==0;	
						}
						if(cnt!=s[0].size())
						{
							g1=1;
							break;
						}
					}
				}
			}
		}
		if(f0&&g1)
		{
			return 1;
		}
		if(f1&&g0)
		{
			return 1;
		}
		return 0;
	}
};
namespace SUB2
{
	bool f0=0,f1=0;
	int use[MAXN],col[MAXN];
	vi s[2];
	void dfs(int now,int fa)
	{
		s[col[now]].pb(now);
		use[now]=1;
		for(int u:v[now])
		{
			if(u==fa)
			{
				continue;
			}
			if(!use[u])
			{
				col[u]=col[now]^1;
				dfs(u,now);
			}
			else
			{
				if(col[u]==col[now])
				{
					f0=1;
				}
				else
				{
					f1=1;
				}
			}
		}
	}
	bool g0=0,g1=0;
	bool check2()
	{
		forn(i,1,n)
		{
			if(!use[i])
			{
				s[0].clear();s[1].clear();
				dfs(i,0);
				if(!g0)
				{
					for(int u:s[0])
					{
						int cnt=0;
						for(int x:v[u])
						{
							cnt+=col[x]==0;	
						}
						if(cnt!=s[0].size()-1)
						{
							g0=1;
							break;
						}
					}
					for(int u:s[1])
					{
						int cnt=0;
						for(int x:v[u])
						{
							cnt+=col[x]==1;	
						}
						if(cnt!=s[1].size()-1)
						{
							g0=1;
							break;
						}
					}
				}
				if(!g1)
				{
					for(int u:s[0])
					{
						int cnt=0;
						for(int x:v[u])
						{
							cnt+=col[x]==1;	
						}
						if(cnt!=s[1].size())
						{
							g1=1;
							break;
						}
					}
					for(int u:s[1])
					{
						int cnt=0;
						for(int x:v[u])
						{
							cnt+=col[x]==0;	
						}
						if(cnt!=s[0].size())
						{
							g1=1;
							break;
						}
					}
				}
			}
		}
		if(f0||f1)
		{
			return 1;
		}
		if(g0&&g1)
		{
			return 1;
		}
		return 0;
	}
};
void solve()
{
	cin>>n>>m;
	forn(i,1,m)
	{
		int x,y;
		cin>>x>>y;
		v[x].pb(y);
		v[y].pb(x);
	}
	if(n<=3)
	{
		cout<<-1<<endl;
		return;
	}
	if(SUB5::check5())
	{
		cout<<5<<endl;
		return;
	}
	if(SUB4::check4())
	{
		cout<<4<<endl;
		return; 
	}
	if(SUB0::check0())
	{
		cout<<0<<endl;
		return;
	}
	if(SUB1::check1())
	{
		cout<<1<<endl;
		return;
	}
	if(SUB2::check2())
	{
		cout<<2<<endl;
		return;
	}
	cout<<3<<endl;
}
/*======================================================================*/
signed main()
{
    cin.tie(0);
    cout.tie(0);
	std::ios::sync_with_stdio(false);
//#define Hank2007
#ifdef Hank2007
	freopen("input.txt","r",stdin);
	freopen("output1.txt","w",stdout);
#endif
  	/*====================================================================*/
  	int TEST_CASE=1;
//	cin>>TEST_CASE;
  	while(TEST_CASE--)
  	{
  		solve();
  	}
  	return 0;
}
/*
//
start coding at
finish debugging at
*/