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

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

struct Blossom {
    int n;
    vector<vector<int>> g;          // adjacency list (1-indexed)
    vector<int> matchTo, parentInTree, baseVertex;
    vector<int> bfsQueue;
    vector<char> isUsedInBFS, isInBlossom;

    explicit Blossom(int n_) : n(n_), g(n_ + 1), matchTo(n_ + 1, 0),
                               parentInTree(n_ + 1, -1), baseVertex(n_ + 1),
                               isUsedInBFS(n_ + 1), isInBlossom(n_ + 1) {
        iota(baseVertex.begin(), baseVertex.end(), 0);
    }

    void addEdge(int u, int v) {
        if (u == v) return;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int lca(int a, int b) {
        vector<char> isVisitedBase(n + 1, 0);
        while (true) {
            a = baseVertex[a];
            isVisitedBase[a] = 1;
            if (matchTo[a] == 0) break;
            a = parentInTree[matchTo[a]];
        }
        while (true) {
            b = baseVertex[b];
            if (isVisitedBase[b]) return b;
            if (matchTo[b] == 0) break;
            b = parentInTree[matchTo[b]];
        }
        return 0; // never reached
    }

    void markPath(int vertex, int commonBase, int child) {
        while (baseVertex[vertex] != commonBase) {
            isInBlossom[ baseVertex[vertex] ] = 1;
            isInBlossom[ baseVertex[ matchTo[vertex] ] ] = 1;
            parentInTree[vertex] = child;
            child = matchTo[vertex];
            vertex = parentInTree[ matchTo[vertex] ];
        }
    }

    void contractBlossom(int v, int u, int commonBase) {
        fill(isInBlossom.begin(), isInBlossom.end(), 0);
        markPath(v, commonBase, u);
        markPath(u, commonBase, v);
        for (int i = 1; i <= n; ++i) {
            if (isInBlossom[ baseVertex[i] ]) {
                baseVertex[i] = commonBase;
                if (!isUsedInBFS[i]) {
                    isUsedInBFS[i] = 1;
                    bfsQueue.push_back(i);
                }
            }
        }
    }

    int findAugmentingPath(int root) {
        fill(isUsedInBFS.begin(), isUsedInBFS.end(), 0);
        fill(parentInTree.begin(), parentInTree.end(), -1);
        iota(baseVertex.begin(), baseVertex.end(), 0);
        bfsQueue.clear();
        bfsQueue.push_back(root);
        isUsedInBFS[root] = 1;
        for (size_t head = 0; head < bfsQueue.size(); ++head) {
            int v = bfsQueue[head];
            for (int u : g[v]) {
                if (baseVertex[v] == baseVertex[u] || matchTo[v] == u) continue;
                if (u == root || (matchTo[u] && parentInTree[matchTo[u]] != -1)) {
                    int a = lca(v, u);
                    contractBlossom(v, u, a);
                } else if (parentInTree[u] == -1) {
                    parentInTree[u] = v;
                    if (matchTo[u] == 0) return u; // found exposed vertex
                    int w = matchTo[u];
                    if (!isUsedInBFS[w]) {
                        isUsedInBFS[w] = 1;
                        bfsQueue.push_back(w);
                    }
                }
            }
        }
        return 0;
    }

    int solve() {
        int matches = 0;
        for (int v = 1; v <= n; ++v) {
            if (matchTo[v] == 0) {
                int u = findAugmentingPath(v);
                if (u == 0) continue;
                ++matches;
                while (u) {
                    int pv = parentInTree[u];
                    int ppv = (pv ? matchTo[pv] : 0);
                    matchTo[u] = pv;
                    if (pv) matchTo[pv] = u;
                    u = ppv;
                }
            }
        }
        return matches;
    }
};

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

    int N, M;
    if (!(cin >> N >> M)) return 0;
    Blossom bl(N);
    for (int i = 0; i < M; ++i) {
        int u, v; cin >> u >> v;
        bl.addEdge(u, v);
    }
    cout << bl.solve() << '\n';
    return 0;
}