!Атомный Кун

const int N = 300005;

int curcol, used[N], covered[N], match[N];
vector<int> g[N];

bool dfs(int v)
{
    used[v] = curcol;
    for (int u : g[v])
        if (match[u] == -1)
        {
            covered[v] = 1;
            match[u] = v;
            return 1;
        }
    for (int u : g[v])
        if (used[match[u]] != curcol && dfs(match[u]))
        {
            covered[v] = 1;
            match[u] = v;
            return 1;
        }
    return 0;
}

void kuhn(int n)
{
    curcol = 0;
    for (int i = 0; i < n; i++)
        used[i] = 0, match[i] = -1, covered[i] = 0;
    while (true)
    {
        curcol++;
        bool ch = 0;
        for (int i = 0; i < n; i++)
            if (!covered[i] && used[i] != curcol)
                ch |= dfs(i);
        if (!ch)
            break;
    }
}