#include <bits/stdc++.h>
using namespace std;

/*
    Problem: House Cleaning

    You are given N houses on a 2D grid.
    Each house is represented by a coordinate (x, y).

    A cleaning employee can be assigned in exactly one of two ways:

    1) Row cleaning:
       The employee cleans all houses having the same x-coordinate.

    2) Column cleaning:
       The employee cleans all houses having the same y-coordinate.

    Every house must be cleaned by at least one employee.

    Your task is to return the minimum number of employees needed.

    ------------------------------------------------------------

    Function:
    int houseCleaning(int input1, vector<vector<int>> input2)

    Parameters:
    - input1 = number of houses
    - input2[i] = {x, y}, the coordinates of the i-th house

    A house is considered covered if:
    - its row is chosen, or
    - its column is chosen

    ------------------------------------------------------------

    Example 1:
    N = 3
    houses = {{0,1}, {0,2}, {1,2}}

    One optimal choice:
    - choose row 0  -> covers (0,1), (0,2)
    - choose col 2  -> covers (0,2), (1,2)

    So answer = 2

    ------------------------------------------------------------

    Example 2:
    N = 4
    houses = {{0,0}, {0,1}, {1,0}, {1,1}}

    We can choose:
    - row 0 and row 1
    or
    - col 0 and col 1

    So answer = 2

    ------------------------------------------------------------

    Main idea:

    Think of this as a bipartite graph.

    - Every distinct row becomes a node on the left side
    - Every distinct column becomes a node on the right side
    - Every house (x, y) becomes an edge between row x and column y

    Now the problem becomes:

    "Choose the minimum number of row/column nodes
     so that every edge is covered."

    That is exactly the Minimum Vertex Cover problem
    in a Bipartite Graph.

    By Kőnig’s theorem:
    Minimum Vertex Cover size = Maximum Matching size

    So we only need to find the maximum matching.

    This code uses the Hopcroft-Karp algorithm for that.

    Time Complexity:
    O(E * sqrt(V)) in practice for bipartite matching

    where:
    - V = number of distinct rows + number of distinct columns
    - E = number of houses
*/

class Solution {
    // graph[u] = list of column nodes connected to row node u
    vector<vector<int>> graph;

    // level[u] is used in BFS phase of Hopcroft-Karp
    vector<int> level;

    // leftMatch[u] = which right-side node is matched with left node u
    // rightMatch[v] = which left-side node is matched with right node v
    // -1 means unmatched
    vector<int> leftMatch, rightMatch;

    // BFS builds layers and checks whether any augmenting path exists
    bool bfs(int leftSize) {
        queue<int> q;

        for (int u = 0; u < leftSize; u++) {
            if (leftMatch[u] == -1) {
                level[u] = 0;
                q.push(u);
            } else {
                level[u] = -1;
            }
        }

        bool foundAugmentingPath = false;

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

            for (int v : graph[u]) {
                int matchedLeft = rightMatch[v];

                // If this right node is free, we found a possible augmenting path
                if (matchedLeft == -1) {
                    foundAugmentingPath = true;
                }
                // Otherwise continue through the matched left node
                else if (level[matchedLeft] == -1) {
                    level[matchedLeft] = level[u] + 1;
                    q.push(matchedLeft);
                }
            }
        }

        return foundAugmentingPath;
    }

    // DFS tries to actually use one augmenting path starting from u
    bool dfs(int u) {
        for (int v : graph[u]) {
            int matchedLeft = rightMatch[v];

            // If v is free, match it directly
            // Otherwise try to reroute the current matched node deeper
            if (matchedLeft == -1 || (level[matchedLeft] == level[u] + 1 && dfs(matchedLeft))) {
                leftMatch[u] = v;
                rightMatch[v] = u;
                return true;
            }
        }

        // No useful path from this node in current BFS layering
        level[u] = -1;
        return false;
    }

public:
    int houseCleaning(int input1, vector<vector<int>> input2) {
        // Compress actual row values and column values into 0-based ids
        unordered_map<int, int> rowId, colId;

        int rowCount = 0, colCount = 0;

        for (auto &house : input2) {
            int x = house[0];
            int y = house[1];

            if (!rowId.count(x)) rowId[x] = rowCount++;
            if (!colId.count(y)) colId[y] = colCount++;
        }

        // Build bipartite graph:
        // row x is connected to column y if house (x, y) exists
        graph.assign(rowCount, {});

        for (auto &house : input2) {
            int u = rowId[house[0]];
            int v = colId[house[1]];
            graph[u].push_back(v);
        }

        // Remove duplicate edges in case same coordinate appears multiple times
        for (int u = 0; u < rowCount; u++) {
            sort(graph[u].begin(), graph[u].end());
            graph[u].erase(unique(graph[u].begin(), graph[u].end()), graph[u].end());
        }

        // Initially no matches
        leftMatch.assign(rowCount, -1);
        rightMatch.assign(colCount, -1);
        level.assign(rowCount, 0);

        int maxMatching = 0;

        // Standard Hopcroft-Karp loop
        while (bfs(rowCount)) {
            for (int u = 0; u < rowCount; u++) {
                if (leftMatch[u] == -1 && dfs(u)) {
                    maxMatching++;
                }
            }
        }

        /*
            By Kőnig’s theorem:
            minimum vertex cover size = maximum matching size

            That is exactly the minimum number of employees needed.
        */
        return maxMatching;
    }
};