1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

struct HopcroftKarp {
    int nL, nR;
    const vector<vector<int>> &adj; // adj[u] -> list of right nodes v
    const vector<bool> *allowL, *allowR;
    vector<int> dist, pairU, pairV;

    HopcroftKarp(int nLeft, int nRight, const vector<vector<int>> &adjRef)
        : nL(nLeft), nR(nRight), adj(adjRef),
          dist(nLeft), pairU(nLeft, -1), pairV(nRight, -1) {}

    bool bfs() {
        queue<int> q;
        for (int u = 0; u < nL; ++u) {
            if (!(*allowL)[u]) { dist[u] = -1; continue; }
            if (pairU[u] == -1) { dist[u] = 0; q.push(u); }
            else dist[u] = -1;
        }
        bool reachableFreeRight = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (!(*allowR)[v]) continue;
                int w = pairV[v];
                if (w != -1 && (*allowL)[w]) {
                    if (dist[w] == -1) {
                        dist[w] = dist[u] + 1;
                        q.push(w);
                    }
                } else if (w == -1) {
                    reachableFreeRight = true;
                }
            }
        }
        return reachableFreeRight;
    }

    bool dfs(int u) {
        for (int v : adj[u]) {
            if (!(*allowR)[v]) continue;
            int w = pairV[v];
            if (w == -1 || ((*allowL)[w] && dist[w] == dist[u] + 1 && dfs(w))) {
                pairU[u] = v;
                pairV[v] = u;
                return true;
            }
        }
        dist[u] = -1;
        return false;
    }

    int maxMatchingWithAllowed(const vector<bool> &allowedLeft, const vector<bool> &allowedRight) {
        allowL = &allowedLeft;
        allowR = &allowedRight;
        fill(pairU.begin(), pairU.end(), -1);
        fill(pairV.begin(), pairV.end(), -1);
        int matching = 0;
        while (bfs()) {
            for (int u = 0; u < nL; ++u) {
                if ((*allowL)[u] && pairU[u] == -1) {
                    if (dfs(u)) ++matching;
                }
            }
        }
        return matching;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<vector<int>> G(n, vector<int>(n, 0));
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        if (u == v) continue;
        G[u][v] = G[v][u] = 1;
    }

    // Build conflict bipartite graph H'
    // Left: 0..n-1, Right: 0..n-1
    vector<vector<int>> adjL(n);
    vector<vector<int>> adjR(n); // reverse neighbors for quick neighbor removal
    // (L[i], R[i])
    for (int i = 0; i < n; ++i) {
        adjL[i].push_back(i);
        adjR[i].push_back(i);
    }
    // (L[u], R[v]) if (u, v) in G
    for (int u = 0; u < n; ++u) {
        for (int v = u + 1; v < n; ++v) {
            if (G[u][v]) {
                adjL[u].push_back(v);
                adjR[v].push_back(u);
                adjL[v].push_back(u);
                adjR[u].push_back(v);
            }
        }
    }

    HopcroftKarp hk(n, n, adjL);

    // Case 1: maximum independent set size (no constraint) = 2n - maxMatching
    vector<bool> allL(n, true), allR(n, true);
    int mm_all = hk.maxMatchingWithAllowed(allL, allR);
    int alpha_all = 2 * n - mm_all;
    if (alpha_all <= n / 2) {
        cout << 1 << '\n';
        return 0;
    }

    // Case 2: enforce both sides non-empty
    int best_both = 0;
    vector<bool> allowL(n), allowR(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            // We can include L[i] and R[j] only if they are NOT adjacent in conflict graph:
            // i != j and (i, j) NOT an edge in G
            if (i == j || G[i][j]) continue;

            fill(allowL.begin(), allowL.end(), true);
            fill(allowR.begin(), allowR.end(), true);

            // Include L[i] and R[j] => remove them and all their neighbors
            allowL[i] = false; // L[i] itself removed from residual (we count +1 manually)
            allowR[j] = false; // R[j] itself removed from residual (we count +1 manually)
            // Remove neighbors of L[i] on Right
            for (int v : adjL[i]) allowR[v] = false;
            // Remove neighbors of R[j] on Left
            for (int u : adjR[j]) allowL[u] = false;

            int cntAllowed = (int)count(allowL.begin(), allowL.end(), true)
                           + (int)count(allowR.begin(), allowR.end(), true);
            int mm_res = hk.maxMatchingWithAllowed(allowL, allowR);
            int alpha_res = cntAllowed - mm_res;   // max ind. set on residual
            int alpha_candidate = 2 + alpha_res;   // +L[i] +R[j]
            if (alpha_candidate > best_both) best_both = alpha_candidate;

            if (best_both > n / 2) {
                cout << -1 << '\n';
                return 0;
            }
        }
    }

    cout << (best_both > n / 2 ? -1 : 1) << '\n';
    return 0;
}