#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);


struct num {
    vector<pair<int, int>> a;

    num() {}
    num(int x, int y) {
        a = { make_pair(x, y) };
    }


    bool is_zero() {
        return a.empty();
    }


    bool is_nonnegative() {
        if (a.empty()) {
            return true;
        }
        return a[0].second > 0;
    }


    bool is_negative() {
        return !is_nonnegative();
    }
};


num operator+(const num& a, const num& b) {
    num c;
    c.a.reserve((int)a.a.size() + (int)b.a.size());
    int i = 0, j = 0;
    while (i < (int)a.a.size() and j < (int)b.a.size()) {
        if (a.a[i].first < b.a[j].first) {
            c.a.push_back(a.a[i]);
            i += 1;
        } else if (a.a[i].first > b.a[j].first) {
            c.a.push_back(b.a[j]);
            j += 1;
        } else if (a.a[i].second + b.a[j].second != 0) {
            c.a.push_back(make_pair(a.a[i].first, a.a[i].second + b.a[j].second));
            i += 1;
            j += 1;
        } else {
            i += 1;
            j += 1;
        }
    }
    while (i < (int)a.a.size()) {
        c.a.push_back(a.a[i]);
        i += 1;
    }
    while (j < (int)b.a.size()) {
        c.a.push_back(b.a[j]);
        j += 1;
    }
    return c;
}


num operator-(const num& a, const num& b) {
    num c;
    c.a.reserve((int)a.a.size() + (int)b.a.size());
    int i = 0, j = 0;
    while (i < (int)a.a.size() and j < (int)b.a.size()) {
        if (a.a[i].first < b.a[j].first) {
            c.a.push_back(a.a[i]);
            i += 1;
        } else if (a.a[i].first > b.a[j].first) {
            c.a.push_back(make_pair(b.a[j].first, -b.a[j].second));
            j += 1;
        } else if (a.a[i].second - b.a[j].second != 0) {
            c.a.push_back(make_pair(a.a[i].first, a.a[i].second - b.a[j].second));
            i += 1;
            j += 1;
        } else {
            i += 1;
            j += 1;
        }
    }
    while (i < (int)a.a.size()) {
        c.a.push_back(a.a[i]);
        i += 1;
    }
    while (j < (int)b.a.size()) {
        c.a.push_back(b.a[j]);
        j += 1;
    }
    return c;
}


bool operator<(const num& a, const num& b) {
    int i = 0, j = 0;
    while (i < (int)a.a.size() and j < (int)b.a.size()) {
        if (a.a[i].first < b.a[j].first) {
            return (a.a[i].second < 0);
        } else if (a.a[i] > b.a[j]) {
            return (b.a[j].second > 0);
        } else if (a.a[i].second - b.a[j].second != 0) {
            return a.a[i].second < b.a[j].second;
        }
        i += 1;
        j += 1;
    }
    if (i < (int)a.a.size()) {
        return a.a[i].second < 0;
    }
    if (j < (int)b.a.size()) {
        return b.a[i].second > 0;
    }
    return false;
}


struct edge {
    int to;
    num w;
    int f, c;
    int rvi;

    edge() {}
    edge(int to, const num& w, int c, int rvi) : to(to), w(w), f(0), c(c), rvi(rvi) {}

    int rest() const {
        return c - f;
    }
};


namespace flow {
    int n;
    int q;
    vector<vector<edge>> g;


    void build(int _n, int _q) {
        n = _n;
        q = _q;
        g.assign(n, vector<edge>());
    }


    void add_edge(int v, int to, int x = -1) {
        int i = (int)g[v].size();
        int j = (int)g[to].size();
        if (x == -1) {
            g[v].push_back(edge(to, num(), 1, j));
            g[to].push_back(edge(v, num(), 0, i));
        } else {
            g[v].push_back(edge(to, num(x, -1), 1, j));
            g[to].push_back(edge(v, num(x, 1), 0, i));
        }
    }


    vector<num> dist;
    vector<int> usd;


    void dijkstra(int s) {
        dist.assign(n, num(-1, 1));
        dist[s] = num();
        usd.assign(n, false);
        usd[s] = true;
        set<pair<num, int>> q;
        q.insert(make_pair(dist[s], s));
        while (!q.empty()) {
            int v = q.begin()->second;
            usd[v] = true;
            q.erase(q.begin());
            for (auto& e : g[v]) {
                int to = e.to;
                if (usd[to] or e.rest() <= 0) {
                    continue;
                }
                if (dist[v] + e.w < dist[to]) {
                    if (dist[to].a.empty() or dist[to].a[0].first != -1) {
                        q.erase(make_pair(dist[to], to));
                    }
                    dist[to] = dist[v] + e.w;
                    q.insert(make_pair(dist[to], to));
                }
            }
        }
    }


    vector<int> pntr;
    vector<int> dist_bfs;

    void bfs(int s) {
        dist_bfs.assign(n, n + 10);
        dist_bfs[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto& e : g[v]) {
                int to = e.to;
                if (e.rest() <= 0 or !e.w.is_zero()) {
                    continue;
                }
                if (dist_bfs[to] > dist_bfs[v] + 1) {
                    dist_bfs[to] = dist_bfs[v] + 1;
                    q.push(to);
                }
            }
        }
    }


    bool dfs1(int v, int t) {
        if (v == t) {
            return true;
        }
        usd[v] = true;
        for (int& i = pntr[v]; i < (int)g[v].size(); i += 1) {
            auto& e = g[v][i];
            int to = e.to;
            if (usd[to] or e.rest() <= 0 or !e.w.is_zero() or dist_bfs[to] != dist_bfs[v] + 1) {
                continue;
            }
            if (dfs1(to, t)) {
                e.f += 1;
                g[to][e.rvi].f -= 1;
                usd[v] = false;
                return true;
            }
        }
        return false;
    }


    bool dfs2(int v, int t) {
        if (v == t) {
            return true;
        }
        usd[v] = true;
        for (int& i = pntr[v]; i < (int)g[v].size(); i += 1) {
            auto& e = g[v][i];
            int to = e.to;
            if (usd[to] or e.rest() <= 0 or !e.w.is_zero()) {
                continue;
            }
            if (dfs2(to, t)) {
                e.f += 1;
                g[to][e.rvi].f -= 1;
                usd[v] = false;
                return true;
            }
        }
        return false;
    }


    vector<int> flow(int s, int t) {
        vector<int> result(q);
        num delta = num();
        int iters = 0;
        while (1) {
            iters += 1;
            assert(iters <= 1000);
            dijkstra(s);
            if (!usd[t]) {
                break;
            }
            delta = delta + dist[t];
            if (delta.is_nonnegative()) {
                break;
            }
            assert((int)delta.a.size() == 1);
            rep(v, n) {
                if (!usd[v]) {
                    continue;
                }
                for (auto& e : g[v]) {
                    int to = e.to;
                    if (!usd[to]) {
                        continue;
                    }
                    e.w = e.w + dist[v] - dist[to];
                }
            }
            bfs(s);
            pntr.assign(n, 0);
            usd.assign(n, false);
            while (1) {
                bool ok = dfs1(s, t);
                if (!ok) {
                    break;
                }
                result[delta.a[0].first] += -delta.a[0].second;
            }
            pntr.assign(n, 0);
            usd.assign(n, false);
            while (1) {
                bool ok = dfs2(s, t);
                if (!ok) {
                    break;
                }
                result[delta.a[0].first] += -delta.a[0].second;
            }
        }
        for (int i = 1; i < q; i += 1) {
            result[i] += result[i - 1];
        }
        return result;
    }
};



int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int n, q;
    cin >> n >> q;
    flow::build(2 * n + 2, q);
    rep(i, n) {
        flow::add_edge(2 * n, i);
        flow::add_edge(n + i, 2 * n + 1);
    }
    rep(i, q) {
        int t;
        cin >> t;
        rep(j, t) {
            int u, v;
            cin >> u >> v;
            --u;
            --v;
            flow::add_edge(u, n + v, i);
        }
    }
    auto result = flow::flow(2 * n, 2 * n + 1);
    assert((int)result.size() == q);
    rep(i, q) {
        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

*/