#include <bits/stdc++.h>
using namespace std;
//https://www.geeksforgeeks.org/maximum-bipartite-matching/
//https://www.geeksforgeeks.org/hopcroft-karp-algorithm-for-maximum-matching-set-1-introduction/

const int INF = 0x3f3f3f3f;

vector<vector<int>> Citire(istream &in, int N, int E)
{
    vector<vector<int> > lisAdiacenta(N + 1);
    for(int i = 1; i <= E; i ++){
        int x, y;
        in >> x >> y;
        lisAdiacenta[x].push_back(y);
    }
    return lisAdiacenta;
}

bool bfs_HopcroftKarp(vector<vector<int> > &lisAdiacenta, vector<int> &stanga, vector<int> &dreapta, vector<int> &distanta)
{
    queue<int> coada;

    for(int i = 1; i < stanga.size(); ++i) {
        if(!stanga[i]) {
            distanta[i] = 0;
            coada.push(i);
        }
        else {
             distanta[i] = INF;
        }
    }
    distanta[0] = INF;

    while(!coada.empty()) {
        int x = coada.front();
        coada.pop();

        if(distanta[x] < distanta[0]) {
            for(int i = 0; i < lisAdiacenta[x].size(); ++i) {
                if(distanta[dreapta[lisAdiacenta[x][i]]] == INF) {
                    distanta[dreapta[lisAdiacenta[x][i]]] = distanta[x] + 1;
                    coada.push(dreapta[lisAdiacenta[x][i]]);
                }
            }
        }
    }

    return (distanta[0] != INF);
}

bool dfs_HopcroftKarp(const int start, vector<vector<int> > &lisAdiacenta, vector<int> &stanga, vector<int> &dreapta, vector<int> &distanta)
{
    if(start) {
        for(int i = 0; i < lisAdiacenta[start].size(); ++i){
            if(distanta[dreapta[lisAdiacenta[start][i]]] == distanta[start]+1) {
                if(dfs_HopcroftKarp(dreapta[lisAdiacenta[start][i]], lisAdiacenta, stanga, dreapta, distanta)){
                    dreapta[lisAdiacenta[start][i]] = start;
                    stanga[start] = lisAdiacenta[start][i];
                    return 1;
                }
            }
        }
        distanta[start] = INF;
        return 0;
    }
    return 1;
}


pair<int, vector<int>> cuplajMaxim(vector<vector<int>> &lisAdiacenta, const int N, const int M)
{
    vector<int> stanga(N + 1, 0), dreapta(M + 1, 0);
    vector<int> distanta(N + 1);
    int rezultat = 0;

    while(bfs_HopcroftKarp(lisAdiacenta, stanga, dreapta, distanta)){
        for(int i = 1; i <= N; ++i) {
            if(!stanga[i] && dfs_HopcroftKarp(i, lisAdiacenta, stanga, dreapta, distanta)) {
                rezultat++;
            }
        }
    }
    return {rezultat, stanga};
}

int main()
{

    return 0;
}