시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 1024 MB | 14 | 4 | 2 | 22.222% |
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$.
3 4 2 1 1 1 2 2 1 1 2 2 2 1 3 3 2 1 3 3
1 2 2 3