题目描述

研究员 Elya 正在维护一张不断增长的带权二分图。图的左右两部分各有 $n$ 个点，两边的点都分别编号为 $1$ 到 $n$。

对于这张图中的一个匹配，若它按下面的字典序意义最优，则称它是贪心匹配：

先在所有匹配中最大化权值为 $1$ 的边数；在此基础上，再最大化权值为 $2$ 的边数；继续这样，对每个权值依次最大化。

换句话说，比较两个匹配时，先看它们使用的权值 $1$ 边数量，数量更多者更优；若相同，再看权值 $2$ 边数量；依此类推。

图中的边按权值从 $1$ 到 $q$ 分批加入。请在每一批加入后，求出只考虑当前已加入边时，贪心匹配的大小，也就是匹配中的边数。

输入格式

第一行包含两个非负整数 $n,q$，分别表示二分图每一侧的点数，以及边权种类数。

接下来包含 $q$ 个块。第 $i$ 个块描述所有权值为 $i$ 的边：

块的第一行包含一个非负整数 $m_i$，表示权值为 $i$ 的边数。

接下来 $m_i$ 行，每行包含两个整数 $x,y$，表示加入一条连接左部点 $x$ 与右部点 $y$ 的边，权值为 $i$。

注意，两点之间可能存在多条边。

输出格式

在一行中输出 $q$ 个整数。第 $i$ 个整数表示只考虑权值不超过 $i$ 的边时，贪心匹配的大小。

数据范围

• $0\le n\le 10^5$；
• $0\le q\le 10^3$；
• $m_i\ge 0$；
• $1\le x,y\le n$；
• $\sum_i m_i\le 2\cdot 10^5$。

样例 1

输入

3 4
2
1 1
1 2
2
1 1
2 2
2
1 3
3 2
1
3 3

输出

1 2 2 3