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

// ===================================================================
// This file contains a collection of algorithms for Maximum Matching
// in Bipartite Graphs, plus all related theorems and constructions
// that frequently appear in ECPC / ACPC problems.
//
// All functions are written as "black boxes". Read the comments above
// each one to understand:
//   - What problem it solves
//   - What input it expects
//   - What it returns
//   - Time complexity
//   - Important constraints / assumptions
//   - Any related concepts (explained in simple English)
// ===================================================================

// ----------------------------- GLOSSARY -----------------------------
// Bipartite Graph     : a graph whose vertices can be split into two
//                       disjoint sets (Left and Right) such that every
//                       edge connects a Left vertex to a Right vertex.
// Matching            : a set of edges with no shared vertices.
// Maximum Matching    : a matching with the largest possible number of
//                       edges.
// Augmenting Path     : a path that starts at an unmatched Left vertex,
//                       ends at an unmatched Right vertex, and alternates
//                       between unmatched and matched edges. Flipping
//                       the edges along this path increases the matching
//                       size by 1.
// Vertex Cover        : a set of vertices that touches every edge.
// Minimum Vertex Cover: the smallest vertex cover. In bipartite graphs,
//                       its size equals the size of the maximum matching
//                       (Kőnig's Theorem).
// Independent Set     : a set of vertices with no edges between them.
// Maximum Independent Set: the largest independent set. In bipartite
//                       graphs, its size = total vertices – size of
//                       minimum vertex cover.
// ===================================================================

// ===================================================================
// 1) Core Hopcroft‑Karp Maximum Bipartite Matching
//    This is the fastest algorithm for maximum matching in bipartite
//    graphs. It processes many augmenting paths in one BFS+DFS phase.
// ===================================================================

// 1.1) Hopcroft‑Karp class (0‑based indexing)
//      PURPOSE:
//        Finds the maximum cardinality matching in a bipartite graph.
//      HOW TO USE:
//        1. Create an object: HopcroftKarp hk(n_left, n_right);
//        2. Add edges: hk.add_edge(u, v);   // u in [0, n_left-1], v in [0, n_right-1]
//        3. Get answer: int match_size = hk.max_matching();
//        4. (Optional) Get the matched partner of each vertex:
//           int left_match[u]  = hk.matchL[u];   // -1 if unmatched
//           int right_match[v] = hk.matchR[v];   // -1 if unmatched
//      TIME COMPLEXITY:
//        O(E * sqrt(V)) where V = n_left + n_right, E = number of edges.
//        This is much faster than the simple O(VE) Kuhn algorithm.
//      CONSTRAINTS:
//        - Graph must be bipartite (edges only from left to right).
//        - Works for up to ~10^5 vertices and ~10^6 edges in practice.
//      NOTES:
//        - Uses 0‑based indexing internally.
//        - If your graph is 1‑based, just subtract 1 when adding edges.
//        - The algorithm is deterministic and returns the same result
//          every time.
struct HopcroftKarp {
    int n_left, n_right;
    vector<vector<int>> adj;          // adjacency list for left vertices
    vector<int> matchL, matchR;       // matchL[u] = v matched to u, -1 if none
    vector<int> dist;                 // distance used in BFS

    HopcroftKarp(int nL, int nR) : n_left(nL), n_right(nR) {
        adj.resize(nL);
        matchL.assign(nL, -1);
        matchR.assign(nR, -1);
        dist.resize(nL);
    }

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

    // BFS: builds layers of the alternating graph.
    // Returns true if there is at least one augmenting path.
    bool bfs() {
        queue<int> q;
        for (int u = 0; u < n_left; u++) {
            if (matchL[u] == -1) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = -1;
            }
        }
        bool found = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                int u2 = matchR[v];
                if (u2 == -1) {
                    found = true;          // we reached an unmatched right vertex
                } else if (dist[u2] == -1) {
                    dist[u2] = dist[u] + 1;
                    q.push(u2);
                }
            }
        }
        return found;
    }

    // DFS: tries to find augmenting paths starting from u.
    bool dfs(int u) {
        for (int v : adj[u]) {
            int u2 = matchR[v];
            if (u2 == -1 || (dist[u2] == dist[u] + 1 && dfs(u2))) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        dist[u] = -1;   // dead end – don't visit again in this phase
        return false;
    }

    // Returns the size of the maximum matching.
    int max_matching() {
        int matching = 0;
        while (bfs()) {
            for (int u = 0; u < n_left; u++) {
                if (matchL[u] == -1 && dfs(u)) {
                    matching++;
                }
            }
        }
        return matching;
    }
};

// ===================================================================
// 2) Minimum Vertex Cover (using the matching from Hopcroft‑Karp)
//    Kőnig's Theorem: In any bipartite graph, the size of the minimum
//    vertex cover equals the size of the maximum matching.
// ===================================================================

// 2.1) Minimum Vertex Cover – returns the set of vertices (as a pair
//      of vectors: left vertices and right vertices) that cover all edges.
//      PURPOSE:
//        Given a bipartite graph, find the smallest set of vertices that
//        touches every edge.
//      HOW TO USE:
//        1. Run HopcroftKarp to get the maximum matching.
//        2. Call min_vertex_cover(hk, n_left, n_right) with the same
//           HopcroftKarp object (after max_matching() has been called).
//      RETURNS:
//        A pair<vector<int>, vector<int>> where the first vector contains
//        the left vertices in the cover, and the second contains the
//        right vertices in the cover.
//      TIME COMPLEXITY:
//        O(V + E) after the matching is computed.
//      CONSTRAINTS:
//        - The HopcroftKarp object must have already computed the matching
//          (i.e., max_matching() was called).
//      NOTES:
//        - The vertex cover is not necessarily unique; this function
//          returns one valid minimum cover.
//        - The size of the cover equals the matching size (you can verify
//          this as a sanity check).
pair<vector<int>, vector<int>> min_vertex_cover(const HopcroftKarp& hk) {
    int nL = hk.n_left, nR = hk.n_right;
    vector<bool> visitedL(nL, false), visitedR(nR, false);
    queue<int> q;

    // Start BFS from all unmatched left vertices
    for (int u = 0; u < nL; u++) {
        if (hk.matchL[u] == -1) {
            visitedL[u] = true;
            q.push(u);
        }
    }

    // BFS on the alternating graph (using the matching)
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : hk.adj[u]) {
            if (!visitedR[v]) {
                visitedR[v] = true;
                int u2 = hk.matchR[v];
                if (u2 != -1 && !visitedL[u2]) {
                    visitedL[u2] = true;
                    q.push(u2);
                }
            }
        }
    }

    // Minimum vertex cover = (Left vertices NOT visited) ∪ (Right vertices visited)
    vector<int> coverL, coverR;
    for (int u = 0; u < nL; u++) {
        if (!visitedL[u]) coverL.push_back(u);
    }
    for (int v = 0; v < nR; v++) {
        if (visitedR[v]) coverR.push_back(v);
    }
    return {coverL, coverR};
}

// ===================================================================
// 3) Maximum Independent Set in a Bipartite Graph
//    In any graph, the complement of a vertex cover is an independent set.
//    So: Max Independent Set = All vertices – Min Vertex Cover.
// ===================================================================

// 3.1) Maximum Independent Set – returns the set of vertices (as a pair
//      of vectors: left and right) that form the largest independent set.
//      PURPOSE:
//        Find the largest set of vertices with no edges between any two
//        of them.
//      HOW TO USE:
//        1. Run HopcroftKarp to get the matching.
//        2. Call max_independent_set(hk) which internally uses the
//           minimum vertex cover from above.
//      RETURNS:
//        A pair<vector<int>, vector<int>> containing the left and right
//        vertices of the maximum independent set.
//      TIME COMPLEXITY:
//        O(V + E) after the matching is computed.
//      CONSTRAINTS:
//        - The HopcroftKarp object must have already computed the matching.
//      NOTES:
//        - The size of the independent set = total vertices – matching size.
//        - This is a classic problem: e.g., "place the maximum number of
//          non‑attacking rooks on a chessboard" often reduces to this.
pair<vector<int>, vector<int>> max_independent_set(const HopcroftKarp& hk) {
    auto cover = min_vertex_cover(hk);
    vector<int> indL, indR;
    // Left independent = left vertices NOT in coverL
    // But careful: coverL contains left vertices that ARE in the cover.
    // So independent left = all left – coverL.
    vector<bool> inCoverL(hk.n_left, false);
    for (int u : cover.first) inCoverL[u] = true;
    for (int u = 0; u < hk.n_left; u++) {
        if (!inCoverL[u]) indL.push_back(u);
    }

    // Right independent = right vertices NOT in coverR
    vector<bool> inCoverR(hk.n_right, false);
    for (int v : cover.second) inCoverR[v] = true;
    for (int v = 0; v < hk.n_right; v++) {
        if (!inCoverR[v]) indR.push_back(v);
    }
    return {indL, indR};
}

// ===================================================================
// 4) Maximum Matching in a Bipartite Graph with 1‑based indexing
//    (wrapper for convenience when the problem uses 1‑based vertices)
// ===================================================================

// 4.1) Same as HopcroftKarp but everything is 1‑based.
//      PURPOSE:
//        Some problems index vertices from 1 to n. This wrapper adjusts
//        the indexing so you can add edges directly with 1‑based numbers.
//      HOW TO USE:
//        1. Create: HopcroftKarp1 hk(n_left, n_right);
//        2. Add edge: hk.add_edge(u, v);   // u in [1..n_left], v in [1..n_right]
//        3. Get answer: int match_size = hk.max_matching();
//        4. Get matches: matchL[u] (1‑based) or matchR[v] (1‑based).
//      TIME COMPLEXITY:
//        Same as the 0‑based version.
//      NOTES:
//        - Internally it converts to 0‑based, so the performance is identical.
//        - The match arrays are 1‑based: matchL[1..n_left], matchR[1..n_right].
struct HopcroftKarp1 {
    int n_left, n_right;
    vector<vector<int>> adj;
    vector<int> matchL, matchR, dist;

    HopcroftKarp1(int nL, int nR) : n_left(nL), n_right(nR) {
        adj.resize(nL + 1);          // 1‑based indexing
        matchL.assign(nL + 1, 0);     // 0 means unmatched
        matchR.assign(nR + 1, 0);
        dist.resize(nL + 1);
    }

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

    bool bfs() {
        queue<int> q;
        for (int u = 1; u <= n_left; u++) {
            if (matchL[u] == 0) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = -1;
            }
        }
        bool found = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                int u2 = matchR[v];
                if (u2 == 0) {
                    found = true;
                } else if (dist[u2] == -1) {
                    dist[u2] = dist[u] + 1;
                    q.push(u2);
                }
            }
        }
        return found;
    }

    bool dfs(int u) {
        for (int v : adj[u]) {
            int u2 = matchR[v];
            if (u2 == 0 || (dist[u2] == dist[u] + 1 && dfs(u2))) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        dist[u] = -1;
        return false;
    }

    int max_matching() {
        int matching = 0;
        while (bfs()) {
            for (int u = 1; u <= n_left; u++) {
                if (matchL[u] == 0 && dfs(u)) {
                    matching++;
                }
            }
        }
        return matching;
    }
};

// ===================================================================
// 5) Maximum Matching in a Bipartite Graph where one side is much smaller
//    (Optimization: run BFS/DFS only on the smaller side)
// ===================================================================

// 5.1) Hopcroft‑Karp that automatically uses the smaller side as "left"
//      to reduce memory and time.
//      PURPOSE:
//        If the graph has, say, 1000 left vertices and 100,000 right
//        vertices, we can swap the sides so that the BFS/DFS run on the
//        smaller side. The matching size is the same.
//      HOW TO USE:
//        1. Create: HopcroftKarpOptimized hk(n_left, n_right);
//        2. Add edge: hk.add_edge(u, v);
//        3. Get matching: hk.max_matching();
//      TIME COMPLEXITY:
//        Same O(E sqrt(V)) but with a smaller constant if one side is tiny.
//      NOTES:
//        - The class internally decides which side is smaller and swaps
//          if needed. You don't need to think about it.
//        - The matchL/matchR arrays still use the original indexing.
struct HopcroftKarpOptimized {
    int nL, nR;
    bool swapped;
    vector<vector<int>> adj;   // adjacency from the side we treat as "left"
    vector<int> matchL, matchR, dist;

    HopcroftKarpOptimized(int n_left, int n_right) {
        if (n_left <= n_right) {
            nL = n_left;
            nR = n_right;
            swapped = false;
        } else {
            nL = n_right;
            nR = n_left;
            swapped = true;
        }
        adj.resize(nL);
        matchL.assign(nL, -1);
        matchR.assign(nR, -1);
        dist.resize(nL);
    }

    void add_edge(int u, int v) {
        if (!swapped) {
            adj[u].push_back(v);
        } else {
            adj[v].push_back(u);   // swap sides
        }
    }

    bool bfs() {
        queue<int> q;
        for (int u = 0; u < nL; u++) {
            if (matchL[u] == -1) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = -1;
            }
        }
        bool found = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                int u2 = matchR[v];
                if (u2 == -1) {
                    found = true;
                } else if (dist[u2] == -1) {
                    dist[u2] = dist[u] + 1;
                    q.push(u2);
                }
            }
        }
        return found;
    }

    bool dfs(int u) {
        for (int v : adj[u]) {
            int u2 = matchR[v];
            if (u2 == -1 || (dist[u2] == dist[u] + 1 && dfs(u2))) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        dist[u] = -1;
        return false;
    }

    int max_matching() {
        int matching = 0;
        while (bfs()) {
            for (int u = 0; u < nL; u++) {
                if (matchL[u] == -1 && dfs(u)) {
                    matching++;
                }
            }
        }
        return matching;
    }

    // Get the matched partner of original vertex u (0‑based)
    int get_match(int u, bool is_left) {
        if (!swapped) {
            return is_left ? matchL[u] : matchR[u];
        } else {
            return is_left ? matchR[u] : matchL[u];
        }
    }
};

// ===================================================================
// 6) Check if a matching is perfect (covers all vertices on one side)
// ===================================================================

// 6.1) Returns true if the matching covers all left vertices.
//      PURPOSE:
//        In many problems (e.g., assignment problems) you need to know
//        if every left vertex can be matched.
//      PARAMETERS:
//        - hk: a HopcroftKarp object after max_matching() has been called.
//      RETURNS:
//        - true if every left vertex is matched, false otherwise.
//      TIME COMPLEXITY:
//        O(n_left)
bool is_perfect_matching_left(const HopcroftKarp& hk) {
    for (int u = 0; u < hk.n_left; u++) {
        if (hk.matchL[u] == -1) return false;
    }
    return true;
}

// 6.2) Returns true if the matching covers all right vertices.
bool is_perfect_matching_right(const HopcroftKarp& hk) {
    for (int v = 0; v < hk.n_right; v++) {
        if (hk.matchR[v] == -1) return false;
    }
    return true;
}

// ===================================================================
// 7) Matching in a graph that is not explicitly bipartite
//    (e.g., grid graphs, chessboard problems)
// ===================================================================

// 7.1) Build a bipartite graph from a grid by colouring cells black/white.
//      PURPOSE:
//        Many problems (like placing dominoes, or knights on a chessboard)
//        can be modelled as matching on a grid. The grid is bipartite
//        by colouring it like a chessboard.
//      HOW TO USE:
//        - For each cell (i,j), compute id = i * cols + j.
//        - If (i+j) is even, it's a "left" vertex; if odd, it's "right".
//        - Add edges between adjacent cells (up/down/left/right).
//      EXAMPLE:
//        int rows, cols;
//        auto id = [&](int i, int j) { return i * cols + j; };
//        HopcroftKarp hk(rows * cols, rows * cols); // upper bound
//        for each cell (i,j) with (i+j)%2 == 0:
//            for each neighbour (ni,nj):
//                hk.add_edge(id(i,j), id(ni,nj));
//        int max_dominoes = hk.max_matching();
//      NOTES:
//        - The matching size gives the maximum number of dominoes (or
//          knights, etc.) that can be placed.
//        - This is a very common ECPC/ACPC pattern.
// ===================================================================

// ===================================================================
// 8) Maximum Matching with Binary Search (parametric matching)
//    Often you need to find the smallest/largest value such that a
//    matching of a certain size exists.
// ===================================================================

// 8.1) Example: Given a threshold X, build a graph using only edges
//      with weight <= X, then check if maximum matching size >= K.
//      PURPOSE:
//        When each edge has a cost/weight and you want the minimum
//        possible maximum weight among a matching of size K.
//      HOW TO USE:
//        1. Sort all edges by weight.
//        2. Binary search on the weight: for a given mid, add only edges
//           with weight <= mid, run Hopcroft‑Karp, check if matching >= K.
//      TIME COMPLEXITY:
//        O(log W * E * sqrt(V)) where W is the range of weights.
//      NOTES:
//        - This is a classic "minimax" problem.
//        - Appears in problems like "assign workers to jobs with minimum
//          maximum cost".
// ===================================================================

// ===================================================================
// 9) Matching with vertex capacities (b‑matching)
//    Sometimes each vertex can be matched more than once.
// ===================================================================

// 9.1) For vertex capacities, you can split each vertex into multiple
//      copies. For example, if a left vertex can be matched up to cap[u]
//      times, create cap[u] copies of that vertex.
//      PURPOSE:
//        Handles problems where each worker can do multiple jobs, or each
//        job needs multiple workers.
//      HOW TO USE:
//        - Build a new graph where each original vertex u is replaced by
//          cap[u] identical vertices.
//        - Run Hopcroft‑Karp on this expanded graph.
//      TIME COMPLEXITY:
//        O(E * sqrt(V)) where V is the total number of copies (sum of caps).
//      NOTES:
//        - This is a simple trick that often appears in ECPC problems.
//        - If the capacities are large (e.g., up to 10^5), this may be
//          too slow – then you need a flow‑based solution.
// ===================================================================

// ===================================================================
// 10) Maximum Matching in a Bipartite Graph with Holes / Missing Edges
//     (e.g., "assign each left to a distinct right, but some pairs forbidden")
// ===================================================================

// 10.1) Standard Hopcroft‑Karp handles missing edges by simply not adding
//       them to the adjacency list. There's no special function needed.
//       Just call add_edge only for allowed pairs.
// ===================================================================

// ===================================================================
// 11) Tricks & Patterns that appeared in ECPC/ACPC
// ===================================================================

// 11.1) (Not a function)
//       "Minimum number of edges to add to make a bipartite graph have
//        a perfect matching" → This is the size of the maximum matching
//        deficit. If max_matching < min(n_left, n_right), you need to add
//        at least min(n_left, n_right) - max_matching edges.
//       This appears in problems like "complete the assignment" or
//       "minimum edges to add for full coverage".

// 11.2) (Not a function)
//       "Maximum matching in a DAG" → A DAG (Directed Acyclic Graph)
//       can be transformed into a bipartite graph by splitting each vertex
//       into a left copy and a right copy. Then maximum matching gives
//       the size of the minimum path cover.
//       This is a very common trick in ECPC/ACPC (e.g., "minimum number
//       of chains to cover all elements").

// 11.3) (Not a function)
//       "Maximum matching with time windows" → Each left vertex can only
//       be matched to a right vertex if a certain time condition holds.
//       Often solved by sorting by time and using a greedy + Hopcroft‑Karp
//       or by building the graph dynamically.

// 11.4) (Not a function)
//       "Maximum bipartite matching with 2‑SAT" → Sometimes the matching
//       must satisfy additional logical constraints. You can first solve
//       the 2‑SAT to determine which edges are possible, then run
//       Hopcroft‑Karp on the resulting graph.

// 11.5) (Not a function)
//       "Counting the number of maximum matchings" – this is #P‑complete
//       in general, but for small graphs you can use DP over subsets.
//       For large graphs, you usually only need the size, not the count.

// 11.6) (Not a function)
//       "Dulmage‑Mendelsohn decomposition" – a way to classify vertices
//       based on the maximum matching. Used in problems that ask for
//       "which edges are in all maximum matchings" or "which vertices
//       are always matched". This is advanced but has appeared in some
//       ACPC problems.

// 11.7) (Not a function)
//       "Maximum matching in a convex bipartite graph" – if the adjacency
//       of each left vertex is a contiguous interval, you can solve it
//       greedily in O(E log V). This is a special case that sometimes
//       appears in ECPC.

// ===================================================================
// 12) Simple Kuhn Algorithm (for small graphs or when simplicity is preferred)
//     O(VE) – use only if V <= 500 or so.
// ===================================================================

// 12.1) Kuhn's algorithm (DFS‑based augmenting path)
//       PURPOSE:
//         Simpler to code than Hopcroft‑Karp, but slower.
//         Use this when the graph is small (V <= 500) or when you need
//         a quick prototype.
//       HOW TO USE:
//         1. Create: Kuhn kuhn(n_left, n_right);
//         2. Add edges: kuhn.add_edge(u, v);
//         3. Get answer: int match_size = kuhn.max_matching();
//       TIME COMPLEXITY:
//         O(VE) in the worst case.
//       CONSTRAINTS:
//         - Works for V up to a few hundred.
//         - Graph must be bipartite.
struct Kuhn {
    int n_left, n_right;
    vector<vector<int>> adj;
    vector<int> matchR, seen;

    Kuhn(int nL, int nR) : n_left(nL), n_right(nR) {
        adj.resize(nL);
        matchR.assign(nR, -1);
    }

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

    bool dfs(int u) {
        for (int v : adj[u]) {
            if (seen[v]) continue;
            seen[v] = 1;
            if (matchR[v] == -1 || dfs(matchR[v])) {
                matchR[v] = u;
                return true;
            }
        }
        return false;
    }

    int max_matching() {
        int matching = 0;
        for (int u = 0; u < n_left; u++) {
            seen.assign(n_right, 0);
            if (dfs(u)) matching++;
        }
        return matching;
    }
};

// ===================================================================
// 13) Maximum Matching in a Bipartite Graph with weights (Assignment Problem)
//     For weighted bipartite matching, use the Hungarian Algorithm.
//     This is NOT Hopcroft‑Karp (which is for unweighted graphs).
//     See the Hungarian Algorithm template for that.
// ===================================================================

// ===================================================================
// main() with example usage (you can ignore this part)
// ===================================================================

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

    // Example: maximum matching in a small graph
    HopcroftKarp hk(3, 3);
    hk.add_edge(0, 0);
    hk.add_edge(0, 1);
    hk.add_edge(1, 1);
    hk.add_edge(2, 2);

    cout << "Maximum matching size: " << hk.max_matching() << '\n'; // 3

    // Example: minimum vertex cover
    auto cover = min_vertex_cover(hk);
    cout << "Vertex cover (left): ";
    for (int u : cover.first) cout << u << " ";
    cout << "\nVertex cover (right): ";
    for (int v : cover.second) cout << v << " ";
    cout << '\n';

    // Example: maximum independent set
    auto indep = max_independent_set(hk);
    cout << "Independent set (left): ";
    for (int u : indep.first) cout << u << " ";
    cout << "\nIndependent set (right): ";
    for (int v : indep.second) cout << v << " ";
    cout << '\n';

    return 0;
}