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

using ll = long long;

// ===================================================================
// This file contains a collection of algorithms related to bipartite
// graphs and assignment problems:
//   - Maximum Bipartite Matching (Kuhn & Hopcroft‑Karp)
//   - Minimum Vertex Cover & Maximum Independent Set (König)
//   - Hungarian Algorithm (Assignment Problem)
//   - Utilities: bipartiteness check, DAG path cover, small‑right matching
// All functions are ready to be used as "black boxes".
// Read the comments above each one to understand:
//   - What it solves
//   - What input it expects
//   - What it returns
//   - Time complexity
//   - Important constraints / assumptions
// ===================================================================

// -------------------------------------------------------------------
// TERMINOLOGY (explained in simple English)
// -------------------------------------------------------------------
// Bipartite graph  : vertices split into Left (L) and Right (R), all edges
//                    connect L to R.
// Matching         : a set of edges with no shared vertices.
// Maximum matching : largest possible number of matching edges.
// Perfect matching : covers every vertex (requires |L| = |R|).
// Alternating path : starts/ends with unmatched edges, alternates.
// Augmenting path  : alternating path from unmatched L to unmatched R.
//                    Flipping its edges increases matching size by 1.
// Vertex cover     : a set of vertices that touches every edge.
// König's theorem  : in bipartite graphs, max matching size = min vertex cover size.
// Independent set  : a set of vertices with no edges between them.
// Assignment problem: assign each left vertex to a distinct right vertex
//                     minimizing total cost (or maximizing profit).
// Hungarian algorithm: solves the assignment problem in O(n³).
// Hopcroft‑Karp   : faster matching algorithm O(E√V).
// ===================================================================

// ===================================================================
// 1) Maximum Bipartite Matching – Kuhn's Algorithm (DFS augmenting)
// ===================================================================

// 1.1) DFS helper for Kuhn. Do not call directly.
//      Tries to find an augmenting path starting from left vertex `v`.
//      Returns true if it succeeds.
bool try_kuhn(int v, const vector<vector<int>>& adj,
              vector<int>& matchR, vector<int>& vis) {
    if (vis[v]) return false;
    vis[v] = 1;
    for (int to : adj[v]) {
        if (matchR[to] == -1 || try_kuhn(matchR[to], adj, matchR, vis)) {
            matchR[to] = v;
            return true;
        }
    }
    return false;
}

// 1.2) Maximum Bipartite Matching using Kuhn's algorithm.
//      INPUT:
//        - n : number of left vertices (0 .. n-1)
//        - m : number of right vertices (0 .. m-1)
//        - adj : adjacency list of size n; adj[i] contains right neighbours
//      OUTPUT:
//        - Returns the size of the maximum matching.
//        - Optionally fills `matchR_out`: matchR[r] = left matched to right r,
//          or -1 if unmatched.
//      TIME COMPLEXITY: O(n * E), where E = total edges.
//                       Fast for n,m <= 5000 in practice.
//      CONSTRAINTS:
//        - Graph must be bipartite (assumed).
//        - Edges are unweighted.
//      NOTES:
//        - Does not modify the input graph.
//        - For larger graphs (n,m up to 50000), use hopcroftKarp().
int maxBipartiteMatching(int n, int m, const vector<vector<int>>& adj,
                         vector<int>* matchR_out = nullptr) {
    vector<int> matchR(m, -1);
    int matching = 0;
    for (int v = 0; v < n; v++) {
        vector<int> vis(n, 0);
        if (try_kuhn(v, adj, matchR, vis))
            matching++;
    }
    if (matchR_out) *matchR_out = matchR;
    return matching;
}

// ===================================================================
// 2) Minimum Vertex Cover in a Bipartite Graph (König's Theorem)
// ===================================================================

// 2.1) Compute a minimum vertex cover given a maximum matching.
//      INPUT:
//        - n, m : sizes of left and right parts
//        - adj  : original adjacency list (left -> right)
//        - matchR : vector of size m from a maximum matching
//      OUTPUT:
//        - Returns a pair (leftCover, rightCover) of vertex IDs.
//      TIME COMPLEXITY: O(n + m + E)
//      CONSTRAINTS:
//        - matchR must be a valid maximum matching.
//      NOTES:
//        - Size of leftCover + rightCover equals matching size.
pair<vector<int>, vector<int>> minVertexCover(
    int n, int m,
    const vector<vector<int>>& adj,
    const vector<int>& matchR) {

    vector<int> matchedLeft(n, 0);
    for (int r = 0; r < m; r++)
        if (matchR[r] != -1)
            matchedLeft[matchR[r]] = 1;

    vector<int> visL(n, 0), visR(m, 0);
    queue<int> q;
    for (int l = 0; l < n; l++) {
        if (!matchedLeft[l]) {
            visL[l] = 1;
            q.push(l);
        }
    }

    while (!q.empty()) {
        int l = q.front(); q.pop();
        for (int r : adj[l]) {
            if (!visR[r]) {
                visR[r] = 1;
                if (matchR[r] != -1 && !visL[matchR[r]]) {
                    visL[matchR[r]] = 1;
                    q.push(matchR[r]);
                }
            }
        }
    }

    vector<int> leftCover, rightCover;
    for (int l = 0; l < n; l++)
        if (!visL[l]) leftCover.push_back(l);
    for (int r = 0; r < m; r++)
        if (visR[r]) rightCover.push_back(r);

    return {leftCover, rightCover};
}

// ===================================================================
// 3) Maximum Independent Set in a Bipartite Graph
// ===================================================================

// 3.1) Compute a maximum independent set.
//      INPUT:
//        - same as minVertexCover (n, m, adj, matchR from a maximum matching)
//      OUTPUT:
//        - Returns a vector of vertex IDs (0 .. n+m-1). Left vertices are
//          encoded as their index; right vertices as n + r.
//      TIME COMPLEXITY: O(n + m + E)
//      NOTES:
//        - Complement of a minimum vertex cover.
//        - Size = (n + m) - matching_size.
vector<int> maxIndependentSet(
    int n, int m,
    const vector<vector<int>>& adj,
    const vector<int>& matchR) {

    auto [lc, rc] = minVertexCover(n, m, adj, matchR);

    vector<int> inCover(n + m, 0);
    for (int l : lc) inCover[l] = 1;
    for (int r : rc) inCover[n + r] = 1;

    vector<int> independent;
    for (int v = 0; v < n + m; v++) {
        if (!inCover[v]) independent.push_back(v);
    }
    return independent;
}

// ===================================================================
// 4) Hungarian Algorithm (Kuhn‑Munkres) for Assignment Problem
// ===================================================================

// 4.1) Solve the minimum cost perfect assignment (square matrix).
//      INPUT:
//        - a : n x n matrix of costs (long long). a[i][j] = cost of
//              assigning left i to right j.
//      OUTPUT:
//        - Returns {min_cost, assignment}. assignment[i] = j means
//          left i is assigned to right j.
//      TIME COMPLEXITY: O(n³)
//      CONSTRAINTS:
//        - n >= 1, matrix must be square.
//        - Costs can be negative (handled correctly).
//      NOTES:
//        - For rectangular matrices, add dummy rows/columns with zero cost.
//        - To maximize profit, see maxWeightAssignment() below.
pair<ll, vector<int>> hungarian(const vector<vector<ll>>& a) {
    int n = (int)a.size();
    int m = (int)a[0].size(); // must be n
    vector<ll> u(n + 1), v(m + 1);
    vector<int> p(m + 1), way(m + 1);

    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int j0 = 0;
        vector<ll> minv(m + 1, LLONG_MAX);
        vector<int> used(m + 1, 0);
        do {
            used[j0] = 1;
            int i0 = p[j0];
            ll delta = LLONG_MAX;
            int j1 = 0;
            for (int j = 1; j <= m; j++) {
                if (!used[j]) {
                    ll cur = a[i0 - 1][j - 1] - u[i0] - v[j];
                    if (cur < minv[j]) {
                        minv[j] = cur;
                        way[j] = j0;
                    }
                    if (minv[j] < delta) {
                        delta = minv[j];
                        j1 = j;
                    }
                }
            }
            for (int j = 0; j <= m; j++) {
                if (used[j]) {
                    u[p[j]] += delta;
                    v[j] -= delta;
                } else {
                    minv[j] -= delta;
                }
            }
            j0 = j1;
        } while (p[j0] != 0);

        // augmenting
        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0);
    }

    vector<int> assignment(n);
    for (int j = 1; j <= m; j++) {
        if (p[j] > 0)
            assignment[p[j] - 1] = j - 1;
    }
    ll cost = 0;
    for (int i = 0; i < n; i++) cost += a[i][assignment[i]];
    return {cost, assignment};
}

// ===================================================================
// 5) Hopcroft‑Karp Algorithm – Faster Maximum Bipartite Matching
// ===================================================================

// 5.1) Hopcroft‑Karp for maximum bipartite matching.
//      INPUT:
//        - n, m, adj (same as Kuhn)
//      OUTPUT:
//        - Returns matching size.
//        - Optionally fills matchR_out.
//      TIME COMPLEXITY: O(E * sqrt(V)) where V = n + m.
//      CONSTRAINTS:
//        - Graph is bipartite.
//      NOTES:
//        - Use this when n,m are large (e.g., 50000) and E moderate.
int hopcroftKarp(int n, int m, const vector<vector<int>>& adj,
                 vector<int>* matchR_out = nullptr) {
    vector<int> pairU(n, -1), pairV(m, -1), dist(n);

    auto bfs = [&]() -> bool {
        queue<int> q;
        for (int u = 0; u < n; u++) {
            if (pairU[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 u_next = pairV[v];
                if (u_next == -1) {
                    found = true;
                } else if (dist[u_next] == -1) {
                    dist[u_next] = dist[u] + 1;
                    q.push(u_next);
                }
            }
        }
        return found;
    };

    function<bool(int)> dfs = [&](int u) -> bool {
        for (int v : adj[u]) {
            int u_next = pairV[v];
            if (u_next == -1 || (dist[u_next] == dist[u] + 1 && dfs(u_next))) {
                pairU[u] = v;
                pairV[v] = u;
                return true;
            }
        }
        dist[u] = -1;
        return false;
    };

    int matching = 0;
    while (bfs()) {
        for (int u = 0; u < n; u++) {
            if (pairU[u] == -1 && dfs(u))
                matching++;
        }
    }

    if (matchR_out) {
        matchR_out->assign(m, -1);
        for (int u = 0; u < n; u++) {
            if (pairU[u] != -1)
                (*matchR_out)[pairU[u]] = u;
        }
    }
    return matching;
}

// ===================================================================
// 6) Utilities for Bipartite Graphs
// ===================================================================

// 6.1) Check if a graph is bipartite and return the two partitions.
//      INPUT:
//        - V : number of vertices (0 .. V-1)
//        - adj : undirected adjacency list (each edge appears twice)
//      OUTPUT:
//        - Returns true if bipartite.
//        - If true, fills `color` with 0/1 for each vertex.
//      TIME COMPLEXITY: O(V + E)
bool isBipartite(int V, const vector<vector<int>>& adj, vector<int>& color) {
    color.assign(V, -1);
    queue<int> q;
    for (int start = 0; start < V; start++) {
        if (color[start] != -1) continue;
        color[start] = 0;
        q.push(start);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) {
                    color[v] = color[u] ^ 1;
                    q.push(v);
                } else if (color[v] == color[u]) {
                    return false;
                }
            }
        }
    }
    return true;
}

// 6.2) Build left adjacency list from an undirected bipartite graph.
//      INPUT:
//        - V, adj, color (from isBipartite, color 0 = left, 1 = right)
//      OUTPUT:
//        - Returns {leftAdj, R}. leftAdj has size L (count of color 0),
//          each entry contains compressed right IDs (0..R-1).
//      TIME COMPLEXITY: O(V + E)
pair<vector<vector<int>>, int> buildBipartiteAdj(
    int V,
    const vector<vector<int>>& adj,
    const vector<int>& color) {

    vector<int> leftId(V, -1), rightId(V, -1);
    int L = 0, R = 0;
    for (int i = 0; i < V; i++) {
        if (color[i] == 0) leftId[i] = L++;
        else rightId[i] = R++;
    }

    vector<vector<int>> leftAdj(L);
    for (int u = 0; u < V; u++) {
        if (color[u] == 0) {
            int l = leftId[u];
            for (int v : adj[u]) {
                if (color[v] == 1) {
                    leftAdj[l].push_back(rightId[v]);
                }
            }
        }
    }
    return {leftAdj, R};
}

// ===================================================================
// 7) Advanced Patterns & Tricks
// ===================================================================

// 7.1) Maximum matching when the right side is very small (m <= 20).
//      INPUT:
//        - n : number of left vertices
//        - m : number of right vertices (must be <= 20)
//        - adjMask : vector of size n, where bit r is set if left i
//                    connects to right r.
//      OUTPUT:
//        - Returns maximum matching size.
//      TIME COMPLEXITY: O(n * 2^m)
//      CONSTRAINTS:
//        - m <= 20 (fits in 32‑bit int).
int maxMatchingSmallRight(int n, int m, const vector<int>& adjMask) {
    int fullMask = 1 << m;
    vector<int> dp(fullMask, -1);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        vector<int> ndp = dp; // skip current left vertex
        for (int mask = 0; mask < fullMask; mask++) {
            if (dp[mask] == -1) continue;
            int available = adjMask[i] & ~mask;
            while (available) {
                int bit = available & -available;
                int newMask = mask | bit;
                ndp[newMask] = max(ndp[newMask], dp[mask] + 1);
                available -= bit;
            }
        }
        dp.swap(ndp);
    }

    int ans = 0;
    for (int mask = 0; mask < fullMask; mask++) ans = max(ans, dp[mask]);
    return ans;
}

// 7.2) Minimum path cover in a Directed Acyclic Graph (DAG).
//      INPUT:
//        - V : number of vertices
//        - dagEdges : vector of (u, v) directed edges (must be a DAG)
//      OUTPUT:
//        - Minimum number of vertex‑disjoint paths to cover all vertices.
//      TIME COMPLEXITY: O(E * sqrt(V)) via Hopcroft‑Karp.
//      NOTES:
//        - By Dilworth's theorem: answer = V - max matching in the
//          bipartite graph built from the DAG.
int minPathCoverDAG(int V, const vector<pair<int,int>>& dagEdges) {
    vector<vector<int>> adj(V);
    for (auto [u, v] : dagEdges) {
        adj[u].push_back(v);
    }
    vector<int> matchR;
    int matching = hopcroftKarp(V, V, adj, &matchR);
    return V - matching;
}

// 7.3a) Maximum matching with forbidden edges: just use allowed edges only.
//       This function is a reminder.
int maxMatchingWithForbidden(int n, int m, const vector<vector<int>>& allowedEdges) {
    return maxBipartiteMatching(n, m, allowedEdges);
}

// 7.3b) Maximum weight perfect assignment (square matrix).
//       INPUT:
//         - cost : n x n matrix of profits (long long)
//       OUTPUT:
//         - Returns {max_profit, assignment}
//       TIME COMPLEXITY: O(n³)
//       NOTES:
//         - If you have a rectangular matrix, add dummy rows/cols with zero.
//         - For minimum cost, use hungarian() directly.
pair<ll, vector<int>> maxWeightAssignment(const vector<vector<ll>>& cost) {
    int n = (int)cost.size();
    vector<vector<ll>> negCost(n, vector<ll>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            negCost[i][j] = -cost[i][j];
    auto [minCost, assign] = hungarian(negCost);
    return {-minCost, assign};
}

// 7.4) Extract matching edges from the matchR array.
//      INPUT:
//        - matchR : vector of size m (right -> left) or -1 if unmatched
//      OUTPUT:
//        - Vector of pairs (left, right) for each matched edge.
vector<pair<int,int>> extractMatchingEdges(const vector<int>& matchR) {
    vector<pair<int,int>> edges;
    for (int r = 0; r < (int)matchR.size(); r++) {
        if (matchR[r] != -1) {
            edges.push_back({matchR[r], r});
        }
    }
    return edges;
}

// ===================================================================
// 8) Example usage (can be removed)
// ===================================================================

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

    // Example: simple bipartite matching
    int n = 2, m = 3;
    vector<vector<int>> adj = {
        {0, 1},
        {1, 2}
    };

    vector<int> matchR;
    int matchSize = maxBipartiteMatching(n, m, adj, &matchR);
    cout << "Maximum matching size: " << matchSize << "\n";
    cout << "Assignments (right -> left):\n";
    for (int r = 0; r < m; r++) {
        cout << "right " << r << " -> left " << matchR[r] << "\n";
    }

    // Minimum vertex cover
    auto [lc, rc] = minVertexCover(n, m, adj, matchR);
    cout << "Min vertex cover left: ";
    for (int l : lc) cout << l << " ";
    cout << "\nMin vertex cover right: ";
    for (int r : rc) cout << r << " ";
    cout << "\n";

    // Independent set
    vector<int> indep = maxIndependentSet(n, m, adj, matchR);
    cout << "Max independent set: ";
    for (int v : indep) {
        if (v < n) cout << "L" << v << " ";
        else cout << "R" << (v - n) << " ";
    }
    cout << "\n";

    // Hungarian example
    vector<vector<ll>> cost = {
        {4, 1, 3},
        {2, 0, 5},
        {3, 2, 2}
    };
    auto [minCost, assign] = hungarian(cost);
    cout << "Min assignment cost: " << minCost << "\n";
    cout << "Assignment: ";
    for (int i = 0; i < (int)assign.size(); i++)
        cout << i << "->" << assign[i] << " ";
    cout << "\n";

    return 0;
}