bool used[MSIZE];
bool matched[MSIZE];
int mt[MSIZE];
vector<int> g[MSIZE];

int Inc(int v) {
    if (used[v]) return false;
    used[v] = true;
    for (int nxt : g[v]) {
        if (mt[nxt] == -1) {
            matched[v] = true;
            mt[nxt] = v;
            return true;
        }
    }

    for (int nxt : g[v]) {
        if (Inc(mt[nxt])) {
            matched[v] = true;
            mt[nxt] = v;
            return true;
        }
    }
    return false;
}

void BuildMT() {
    memset(matched, 0, sizeof matched);
    fill(mt, mt + MSIZE, -1);
    for (int run = 1; run; ) {
        run = 0;
        memset(used, 0, sizeof used);
        for (int i = 0; i < MSIZE; i++) {
            if (!matched[i] && Inc(i)) {
                run = 1;
            }
        }
    }
}