그리디 이분 매칭

왼쪽 부분에 $n$개, 오른쪽 부분에 $n$개, 총 $2n$개의 정점을 가진 가중치가 있는 이분 그래프를 생각한다. 각 부분의 정점은 1부터 $n$까지 번호가 매겨져 있다. 모든 매칭 중에서 가중치 1인 간선 수가 최대인 매칭을 고르고, 그중에서 가중치 2인 간선 수가 최대인 매칭을 고르는 식으로 차례로 최대화한 매칭을 greedy 매칭이라고 한다.

이 문제의 목표는 간선이 계속 추가되는 그래프에서 greedy 매칭의 크기(간선 수)를 구하는 것이다.

첫 줄에 음이 아닌 정수 $n$과 $q$ ($n \leq 10^5$, $q \leq 10^3$)가 주어진다. 각각 한 부분의 정점 수와 간선 가중치의 종류 수이다.

이어서 $q$개의 블록이 주어진다. $i$번째 블록은 가중치가 $i$인 간선의 개수 $m_i$로 시작한다. 다음 $m_i$개의 줄에는 정수 $x$, $y$ ($1 \leq x, y \leq n$)가 한 줄에 하나씩 주어지며, 왼쪽 정점 $x$와 오른쪽 정점 $y$ 사이에 간선을 추가한다. $\sum m_i \leq 2 \cdot 10^5$이 보장된다.

같은 두 정점 사이에 간선이 여러 개 있을 수 있다.

한 줄에 $q$개의 정수를 출력한다. 가중치가 1 이하인 간선만 볼 때의 답, 2 이하일 때의 답, ..., $q$ 이하일 때의 답을 차례로 출력한다.