#pragma GCC Optimaze("Ofast")
#pragma GCC target("avx,avx2")

#include <bits/stdc++.h>

#define all(x) (x).begin(),(x).end()

const int N = 3e4;

using namespace std;
using bs = bitset<N>;

bs g[N];
int n;
bool used[N];
bool matched[N];
int mt[N];

bool Inc(int v) {
    if (used[v]) return false;
    used[v] = true;
    for (auto i = g[v]._Find_first(); i < n; i = g[v]._Find_next(i)) {
        if (mt[i] == -1) {
            matched[v] = true;
            mt[i] = v;
            return true;
        }
    }
    for (auto i = g[v]._Find_first(); i < n; i = g[v]._Find_next(i)) {
        if (Inc(mt[i])) {
            matched[v] = true;
            mt[i] = v;
            return true;
        }
    }
    return false;
}

mt19937 rnd(random_device{}());

int GetMT() {
    memset(matched, 0, sizeof matched);
    fill(mt, mt + N, -1);
    int cur = 0;
    vector<int> indexes(n);
    iota(all(indexes), 0);
    for (int run = 1; run;) {
        run = 0;
        shuffle(all(indexes), rnd);
        memset(used, 0, sizeof used);
        for (int i: indexes) {
            if (!matched[i] && Inc(i)) {
                cur++;
                run = 1;
            }
        }
    }
    return cur;
}

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

}