#include <iostream>
#include <queue>
#include <vector>

using namespace std;
const int inf = 1e9;

//bfs используем для поиска вершин, которые еще не лежат в пар.соче.
bool bfs(const vector<vector<int>> &graph, vector<int> &available, vector<int> &match, int len)
{
    queue<int> q;

    //помечаем 0 все доступные вершины, т.е те, которые не взяты в пар.соч., те вершины, что в пар.соче. помечаем inf
    for (int i = 1; i < len; ++i)
    {
        if (match[i] == 0)
        {
            available[i] = 0;
            q.push(i);

        }
        else available[i] = inf;
    }

    available[0] = inf;

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

        if (v == 0) continue;

        for (int u : graph[v])
        {
            //если смежная вершина для right == inf, то это говорит о том, что right нигде не задействована,
            //а значит в нее можно попасть только из left
            if (available[match[u]] == inf)
            {

                cout << '\n';
                for (int it : available)
                    cout << it << " ";
                cout << '\n';

                available[match[u]] = available[v] + 1;
                q.push(match[u]);
            }

        }
    }

    return (available[0] != inf); //если available[0] == inf, то это означает, что нам никак не добраться до фиктивной вершины с помошью
    //увеличивающихся путей, а значит увелчивающихся путей просто нет, то есть найдено максимальное паросочетание
}

//ишем увел.путь
bool dfs(const vector<vector<int>> &graph, vector<int> &available, vector<int> &match, int v)
{
    if (v == 0) return 1;

    for (int u : graph[v])
    {
        if (available[match[u]] == available[v] + 1 && dfs(graph, available, match, match[u]))
        {
            //увеличивающийся путь переходит в чередующийся
            match[u] = v;
            match[v] = u;
            //std::cout << "\nCurrent Matching; left: " << v << ", right: " << u;

            return 1;
        }
    }

    available[v] = inf; //помечаем, что нет увел.путь начинающегося с вершины left, больше отсюда не пробуем искать увел.пути

    return 0;
}

int hopcroftKarp(const vector<vector<int>> &graph)
{
    int n = graph.size();
    int ans = 0;

    vector<int> match(n, 0);
    vector<int> available(n, 0);

    while (bfs(graph, available, match, n)) //пока есть увел.путь
        for (int i = 1; i < n; ++i)
            if (match[i] == 0 && dfs(graph, available, match, i))
                ans++;

    return ans;
}


int main()
{

    vector<vector<int>> graph(11);

    graph[1].push_back(6);
    graph[1].push_back(7);
    graph[1].push_back(9);

    graph[2].push_back(7);
    graph[2].push_back(8);
    graph[2].push_back(9);

    graph[3].push_back(10);

    graph[5].push_back(9);

    cout << "\nMax matching: " << hopcroftKarp(graph) << '\n';


    vector<vector<int>> graph2(9);

    graph2[5].push_back(1);
    graph2[5].push_back(2);
    graph2[5].push_back(3);
    graph2[5].push_back(4);

    graph2[6].push_back(1);
    graph2[6].push_back(2);
    graph2[6].push_back(3);
    graph2[6].push_back(4);

    cout << "\nMax matching: " << hopcroftKarp(graph2) << '\n';


    vector<vector<int>> graph3(7);

    graph3[1].push_back(4);
    graph3[1].push_back(5);
    graph3[1].push_back(6);

    graph3[2].push_back(4);

    graph3[3].push_back(5);
    graph3[3].push_back(6);

    cout << "\nMax matching: " << hopcroftKarp(graph3) << '\n';

    return 0;
}