Greedy Bipartite Matching

Consider a bipartite weighted graph with $2n$ vertices: $n$ in the left part and $n$ in the right part. The vertices in each part are numbered from $1$ to $n$. A matching is called greedy if it has the maximal number of edges of weight $1$ among all matchings, the maximal number of edges of weight $2$ among all matchings that maximize the number of edges of weight $1$, and so on.

The goal is to find the size (number of edges) of a greedy matching in a graph that keeps growing.

The first line contains two non-negative integers $n$ and $q$ ($n \leq 10^5$, $q \leq 10^3$): the number of vertices in each part and the number of different edge weights.

Then the input consists of $q$ blocks. The $i$-th block starts with a non-negative integer $m_i$, the number of edges of weight $i$. Each of the next $m_i$ lines contains two integers $x$ and $y$ ($1 \leq x, y \leq n$), which add an edge between vertex $x$ of the left part and vertex $y$ of the right part. It is guaranteed that $\sum m_i \leq 2 \cdot 10^5$.

There may be multiple edges between the same two vertices.

Output $q$ integers on a single line: the answers for weights at most $1$, weights at most $2$, ..., weights at most $q$.