#include <bits/stdc++.h>
using namespace std;
int fa[2005], n, m, graph[1005][1005], vis[1005], tot, sz[1005], dp[1005][2005];
int fnd(int x)
{
    if(fa[x] == x) return x;
    return fa[x] = fnd(fa[x]);
}
void cup(int x, int y)
{
    x = fnd(x), y = fnd(y);
    fa[y] = x;
}
int main()
{
    scanf("%d%d", &n, &m);
    memset(vis, -1, sizeof(vis));
    for(int i = 1; i <= 2 * n; i++)
        fa[i] = i;
    for(int i = 1, u, v; i <= m; i++){
        scanf("%d%d", &u, &v);
        graph[u][v] = graph[v][u] = 1;
    }
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            if(!graph[i][j]){
                if(fnd(i) == fnd(j)){
                    printf("-1\n");
                    return 0;
                }
                cup(i, j + n); cup(j, i + n);
            }
    for(int i = 1; i <= n; i++){
        if(!~vis[fnd(i)] && !~vis[fnd(i + n)])
            vis[fnd(i)] = tot++;
        if(~vis[fnd(i)]) sz[vis[fnd(i)]]++;
        else sz[vis[fnd(i + n)]]--;
    }
    dp[0][n] = 1;
    for(int i = 0; i < tot; i++)
        for(int j = 0; j <= 2 * n; j++)
            if(dp[i][j])
                dp[i + 1][j + sz[i]] = dp[i + 1][j - sz[i]] = 1;
    int ans = 0;
    while(!dp[tot][n + ans]) ans++;
    printf("%d\n", ans);
    return 0;
}