const int NIL = 0;
const int INF = 1e9;
class BipartiteGraph {
    int m, n; // Number of vertices in left and right partitions
    std::vector<std::list<int>> adj; // Adjacency list
    std::vector<int> pairU, pairV, dist; // Matching arrays and distance array

public:
    BipartiteGraph(int m, int n) : m(m), n(n) {
        adj.resize(m + 1);
        pairU.resize(m + 1);
        pairV.resize(n + 1);
        dist.resize(m + 1);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    bool bfs() {
        std::queue<int> q;
        for (int u = 1; u <= m; ++u) {
            if (pairU[u] == NIL) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = INF;
            }
        }
        dist[NIL] = INF; // Special case for NIL

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            if (dist[u] < dist[NIL]) {
                for (int v : adj[u]) {
                    if (dist[pairV[v]] == INF) {
                        dist[pairV[v]] = dist[u] + 1;
                        q.push(pairV[v]);
                    }
                }
            }
        }
        return (dist[NIL] != INF);
    }

    bool dfs(int u) {
        if (u == NIL) return true;

        for (int v : adj[u]) {
            if (dist[pairV[v]] == dist[u] + 1) {
                if (dfs(pairV[v])) {
                    pairV[v] = u;
                    pairU[u] = v;
                    return true;
                }
            }
        }
        dist[u] = INF; // Mark as visited in this phase
        return false;
    }

    int hopcroftKarp() {
        int result = 0;
        while (bfs()) {
            for (int u = 1; u <= m; ++u) {
                if (pairU[u] == NIL && dfs(u)) {
                    result++;
                }
            }
        }
        return result;
    }
};