#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
template<class T1,class T2> bool cmax(T1 &x,const T2 &y) { if (x<y) { x=y; return 1; }return 0; }
#define all(x) (x).begin(),(x).end()
ll triple(int n,const vector<pair<int,int>> &edges)
{
	vector<int> d(n),id(d),rk(d),cnt(d);
	vector e(n,vector<int>(0,0));
	for (auto [u,v]:edges) ++d[u],++d[v];
	iota(all(id),0); sort(all(id),[&](int x,int y) { return d[x]<d[y]; });
	for (auto [u,v]:edges)
	{
		if (rk[u]>rk[v]) swap(u,v);
		e[u].push_back(v);
	}
	ll ans=0;
	for (int i=0; i<n; i++)
	{
		for (int u:e[i]) cnt[u]=1;
		for (int u:e[i]) for (int v:e[u]) ans+=cnt[v];
		for (int u:e[i]) cnt[u]=0;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	auto solve=[&]()
		{
			int n,m,i,j;
			cin>>n>>m;
			if (n<4) return -1;
			vector e(n+1,vector<int>());
			vector<int> dep(n+1),ed(n+1),f(n+1);
			vector<int> flg(2);
			vector<pair<int,int>> edges(m);
			for (auto &[u,v]:edges)
			{
				cin>>u>>v;
				e[u].push_back(v);
				e[v--].push_back(u--);
			}
			ll ans=triple(n,edges);
			function<void(int)> dfs=[&](int u)
				{
					ed[u]=1;
					for (int v:e[u]) if (!ed[v])
					{
						f[v]=u;
						dep[v]=dep[u]+1;
						dfs(v);
					}
					else if (v!=f[u])
					{
						flg[(dep[u]^dep[v]^1)&1]=1;
					}
				};
			for (i=1; i<=n; i++) if (!ed[i]) dfs(i);
			if (flg[0]&&flg[1]) return 0;
			if (flg[0]) return 1;
			ans*=3;
			for (auto [u,v]:edges)
			{
				++u; ++v;
				ans-=(e[u].size()-1ll)*(e[v].size()-1);
			}
			// ans=0;
			if (flg[1])
			{
				if (ans) return 1;
				return 2;
			}
			if (ans) return 2;
			for (i=1; i<=n; i++) if (e[i].size()>=3) return 2;
			iota(all(f),0);
			vector<int> sz(n,1);
			function<int(int)> getf=[&](int u) { return f[u]==u?u:f[u]=getf(f[u]); };
			for (auto [u,v]:edges)
			{
				u=getf(u); v=getf(v);
				if (u!=v)
				{
					sz[v]+=sz[u];
					f[u]=v;
				}
			}
			vector<int> szz;
			for (i=0; i<n; i++) if (f[i]==i) szz.push_back(sz[i]);
			sort(all(szz),greater<>());
			int cur=0;
			for (i=0; i<szz.size(); i++) if ((cur+=sz[i])>=4) break;
			return i+2;
		};
	cout<<solve()<<endl;
}