#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5 , M = N * 2;
int n , m , dep[N] , mx[N];
int num , dfn[N] , low[N];
int cnt , col[N] , sz[N] , deg[N];
int tot = 1 , head[N];
struct Edge{int to , nxt;}e[M * 2];
bool bridge[M * 2] , even , odd , chain;
void Add(int u , int v){e[++tot] = {v , head[u]} , head[u] = tot;}
void Dfs(int u , int fa)
{
	low[u] = dfn[u] = ++num;
	dep[u] = dep[fa] + 1 , mx[u] = 0;
	for(int i = head[u] ; i ; i = e[i].nxt)
	{
		int v = e[i].to;
		if(v == fa)continue ;
		if(!dfn[v])
		{
			Dfs(v , u);
			if(mx[u] + mx[v] + 1 > 3)chain = 1;
			mx[u] = max(mx[u] , mx[v] + 1);
			low[u] = min(low[u] , low[v]);
			if(dfn[u] < low[v])
				bridge[i] = bridge[i ^ 1] = 1;
		}
		else 
		{
			low[u] = min(low[u] , dfn[v]);
			int len = dep[u] - dep[v] + 1;
			if(len & 1)odd = 1;
			else even = 1;
		}
	}
}
void Dfs2(int u)
{
	col[u] = cnt , sz[cnt]++;
	for(int i = head[u] ; i ; i = e[i].nxt)
	{
		int v = e[i].to;
		if(!bridge[i] && !col[v])Dfs2(v);
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0) , cout.tie(0);
	cin >> n >> m;
	for(int i = 1 ; i <= m ; i++)
	{
		int u , v; cin >> u >> v;
		Add(u , v) , Add(v , u);
	}
	if(n <= 3)return cout << "-1\n" , 0;
	if(m <= 2)return cout << 5 - m << "\n" , 0;
	for(int i = 1 ; i <= n ; i++)
		if(!dfn[i])Dfs(i , 0);
	for(int i = 1 ; i <= n ; i++)
		if(!col[i])cnt++ , Dfs2(i);
	for(int i = 2 ; i <= tot ; i += 2)
	{
		int u = e[i ^ 1].to , v = e[i].to;
		if(col[u] == col[v])deg[u]++ , deg[v]++;
	}
	for(int i = 1 ; i <= cnt ; i++)
	{
		if(sz[i] >= 3)
		{
			if(sz[i] & 1)odd = 1;
			else even = 1;
		}
	}
	for(int i = 1 ; i <= n ; i++)
		if(sz[col[i]] > 3 && deg[i] > 2)even = 1;
	if(odd && even)cout << "0\n";
	else if(even)cout << "1\n";
	else if(odd)cout << 2 - chain << "\n";
	else cout << 3 - chain << "\n";
	return 0;
}