28178번 - Greedy Bipartite Matching 다국어

문제

Consider a bipartite weighted graph with 2ドル n$ 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ドル,ドル etc.

Your task is to find the size (number of edges) of greedy matching in a dynamically growing graph.

입력

The first line of the input 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 weights of the edges.

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_i m_i \leq 2 \cdot 10^5$.

Note that there may be multiple edges between two vertices.

출력

You have to output $q$ integers on a single line: answers for the problem for weights at most 1ドル,ドル weights at most 2ドル,ドル \ldots, weights at most $q$.

제한

힌트