#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int N = 1 << 17;

template<typename T>
void updMin(T& a, T b)
{
	a = min(a, b);
}

template<typename T>
void updMax(T& a, T b)
{
	a = max(a, b);
}

VI g[N];
int d[N];
int delta[N];

bool oddCycle, evenCycle, triangle, bigOddCycle;
int szComp, maxDeg;

int dfs(int v, int p)
{
	szComp++;
	updMax(maxDeg, SZ(g[v]));
	int subtreeSum = 0;
	for (int to : g[v])
	{
		if (to == p)
			continue;
		if (d[to] != -1)
		{
			if ((d[v] - d[to]) % 2 == 0)
			{
				oddCycle = true;
				if (d[v] - d[to] == 2)
					triangle = true;
				else
					bigOddCycle = true;
				delta[v]++;
				delta[to]--;
			}
			else
			{
				evenCycle = true;
			}
		}
		else
		{
			d[to] = d[v] + 1;
			subtreeSum += dfs(to, v);
		}
	}
	subtreeSum += delta[v];
	if (subtreeSum > 1)
		evenCycle = true;
	return subtreeSum;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	if (n < 4)
	{
		cout << "-1\n";
		return 0;
	}
	if (m <= 1)
	{
		cout << 5 - m << "\n";
		return 0;
	}
	FOR(i, 0, m)
	{
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		g[u].PB(v);
		g[v].PB(u);
	}
	fill(d, d + n, -1);
	int ans = 3;
	bool oddCycleInGraph = false;
	bool evenCycleInGraph = false;
	bool triangleInGraph = false;
	bool longChainInGraph = false;
	int maxComp = 0;
	FOR(i, 0, n)
	{
		if (d[i] == -1)
		{
			oddCycle = evenCycle = triangle = bigOddCycle = false;
			szComp = 0;
			maxDeg = 0;
			d[i] = 0;
			dfs(i, -1);
			if (evenCycle || bigOddCycle)
				updMin(ans, 1);
			if (triangle && szComp > 3)
				updMin(ans, 1);
			triangleInGraph |= triangle;
			longChainInGraph |= szComp > 3 && maxDeg < szComp - 1;
			updMax(maxComp, szComp);
			oddCycleInGraph |= oddCycle;
			evenCycleInGraph |= evenCycle;
		}
	}
	if (oddCycleInGraph && evenCycleInGraph)
		updMin(ans, 0);
	if (triangleInGraph && longChainInGraph)
		updMin(ans, 1);
	if (triangleInGraph)
		updMin(ans, 2);
	if (maxComp >= 4)
		updMin(ans, 2);
	cout << ans << "\n";
	return 0;
}