#include <bits/stdc++.h>
using namespace std;
const int N = 200005; 

int n, m, ans, odd, even, chaingeq3;
int dep[N], sum[N], xx[N], yy[N];
vector<int> G[N];

void dfs(int x, int fa) {
    dep[x] = dep[fa] + 1;
    for (int y : G[x]) if (y != fa) {
        if (dep[y] == 0) { dfs(y, x); continue; }
        if ((dep[x] + dep[y]) & 1) even = 1; 
        else odd = 1; 
        if (dep[y] < dep[x]) ++sum[x], --sum[y]; 
    }
}
void calc(int x, int fa) {
    for (int y : G[x]) if (dep[y] == dep[x] + 1) calc(y, x), sum[x] += sum[y]; 
    if (sum[x] > 1) even = 1; 
}

int main(void) {
    cin >> n >> m; 
    if (n <= 3) return cout << "-1\n", 0; 
    for (int i = 1, x, y; i <= m; ++i)
        cin >> x >> y, G[x].emplace_back(y), G[y].emplace_back(x), xx[i] = x, yy[i] = y;
    for (int i = 1; i <= n; ++i) if (dep[i] == 0) dfs(i, 0), calc(i, 0); 
    if (m <= 2) return cout << 5 - m << "\n", 0; 
    if (odd && even) return cout << "0\n", 0; 
    for (int i = 1; i <= m && chaingeq3 == 0; ++i) {
        int x = xx[i], y = yy[i];
        if (G[x].size() > 1 && G[y].size() > 1)
            for (int a : G[x]) for (int b : G[y]) if (a != b && a != x && b != y)
                chaingeq3 = 1; 
    }
    if (even || (odd && chaingeq3)) return cout << "1\n", 0; 
    cout << "2\n"; 
    return 0; 
}