Kuhn.cpp

#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
using namespace std;

typedef int ll;
namespace Mlxa
{
    #define read cin
    #define eol '\n'
    #define endln cout << eol

    template <class A> inline void print (A a) { cout << a << ' '; }
    template <class A> inline void println (A a) { cout << a << eol; }
    template <class A, class... B> inline void println (A a, B... b) { print(a), println(b...); }
    template <class A> void printseq (A b, A e) { for (A i(b); i != e; ++ i) print(*i); endln; }
    #define w(...) println(__VA_ARGS__)
    #ifdef AC
        #define ndb(a) println("[NDB]", #a, "=", a)
        #define db(...) println("[MDB]", __VA_ARGS__)
    #else
        #define ndb(a) ((void)0)
        #define db(...) ((void)0)
    #endif
    #define fastIO cin.tie(nullptr), ios_base::sync_with_stdio(false)
    #define all(x) begin(x), end(x)
    #define pb push_back
} using namespace Mlxa;

const ll N(2019);
ll n, m;

typedef set<ll> Graph[N]; // vector?
Graph G, H;

ll mt[N];
char used[N];
char cused[N];

bool kun (ll v)
{
    if (used[v] || cused[v]) return false;
    cused[v] = true;
    for (ll to : H[v])
    if (mt[to] < 0 || kun(mt[to])) {
        mt[to] = v;
        return true;
    }   return false;
}

ll pairSize(0);

ll countWays (ll i)
{
    fill(cused, cused + N, 0);
    if (kun(i)) ++ pairSize, used[i] = true;
    ll ans = n - pairSize;
    return ans;
}

int main ()
{
    fastIO;
    fill(mt, mt + N, -1);
    fill(used, used + N, 0);
    read >> n >> m;
    for (ll i, j, k(m); k --; ) {
        read >> i >> j;
        H[i].insert(j + n);
        H[j].insert(i + n);
        print(countWays(i));
    } endln;
    return 0;
}