#pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>

using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)


const ll inf = 1e18;
mt19937 rnd(234);


int n, q;
vector<vector<int>> g;
vector<vector<pair<int, int>>> edges;
vector<int> result;
vector<int> is_good_left, is_good_right, good_left;
int usdc;
vector<int> usd;
vector<int> p;
vector<int> usd_left;


bool dfs(int v) {
    usd[v] = usdc;
    for (auto to : g[v]) {
        if (p[to] == -1) {
            p[to] = v;
            usd_left[v] = true;
            return true;
        }
        if (usd[p[to]] == usdc) {
            continue;
        }
        if (dfs(p[to])) {
            p[to] = v;
            usd_left[v] = true;
            return true;
        }
    }
    return false;
}


void solve() {
    is_good_left.assign(n, true);
    is_good_right.assign(n, true);
    good_left.resize(n);
    rep(i, n) good_left[i] = i;
    usd.assign(n, 0);
    usdc = 1;
    g.assign(n, vector<int>());
    result.resize(q);
    p.assign(n, -1);
    int cur_matching = 0;
    usd_left.assign(n, false);
    rep(eid, q) {
        for (auto [u, v] : edges[eid]) {
            if (is_good_left[u] and is_good_right[v]) {
                g[u].push_back(v);
            }
        }
        ++usdc;
        for (auto v : good_left) {
            if (usd_left[v]) {
                continue;
            }
            if (dfs(v)) {
                cur_matching += 1;
                ++usdc;
            }
        }
        result[eid] = cur_matching;
        if (eid + 1 == q) {
            break;
        }
        ++usdc;
        queue<int> q;
        for (auto v : good_left) {
            if (usd_left[v]) {
                continue;
            }
            q.push(v);
            usd[v] = usdc;
        }
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto to : g[v]) {
                assert(p[to] != -1);
                is_good_right[to] = false;
                if (usd[p[to]] == usdc) {
                    continue;
                }
                usd[p[to]] = usdc;
                q.push(p[to]);
            }
        }
        vector<int> new_good_left;
        for (auto v : good_left) {
            if (usd[v] == usdc) {
                new_good_left.push_back(v);
            } else {
                is_good_left[v] = false;
            }
        }
        good_left.swap(new_good_left);
    }
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n >> q;
    edges.assign(q, vector<pair<int, int>>());
    rep(i, q) {
        int t;
        cin >> t;
        edges[i].resize(t);
        rep(j, t) {
            int u, v;
            cin >> u >> v;
            --u;
            --v;
            edges[i][j] = make_pair(u, v);
        }
    }
    solve();
    for (int i = 0; i < q; i += 1) {
        cout << result[i] << " ";
    }
    cout << "\n";
    return 0;
}


/*
3 4
2
1 1
1 2
2
1 1
2 2
2
1 3
3 2
1
3 3

*/