#include <vector>
#include <iostream>
#include <iomanip>

using namespace std;

vector<vector<int>> p1 = { {0,4,2,2},{6,0,0,4},{0,0,6,4},{8,4,0,0}};
vector<vector<int>> p2 = { {0,6,4,4},{4,0,0,4},{0,2,8,6},{6,4,0,0}};

vector<vector<int>> bipartee(const vector<vector<int>>& q)
{
    vector<vector<int>> p;
    for(size_t r = 0; r < q.size(); ++r)
    {
        p.push_back(vector<int>());
        for(size_t c = 0; c < q.size(); ++c)
            if (q[r][c] == 0) p[r].push_back(c);
    }
    return p;
}

bool try_kuhn(int v, vector<vector<int>>& g, vector<int>& mt, vector<bool>& used)
{
    if (used[v])  return false;
    used[v] = true;
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (mt[to] == -1 || try_kuhn(mt[to],g,mt,used))
        {
            mt[to] = v;
            return true;
        }
    }
    return false;
}

bool check(const vector<vector<int>>& p)
{
    int n = p.size();
    vector<vector<int>> g = bipartee(p);
    vector<int> mt;
    vector<bool> used;
    mt.assign(n, -1);
    for(int v = 0; v < n; ++v) {
        used.assign(n,false);
        try_kuhn(v,g,mt,used);
    }

    int sum = 0;
    for (int i=0; i<n; ++i)
        if (mt[i] != -1) ++sum;
    return (sum == n);
}


int main()
{
    cout << "First matrix: "  << check(p1) << endl;
    cout << "Second matrix: " << check(p2) << endl;
}