考虑一个二分加权图，共有 $2n$ 个顶点：左侧部分有 $n$ 个顶点，右侧部分有 $n$ 个顶点。每一侧的顶点编号均为 $1$ 到 $n$。如果一个匹配在所有匹配中包含权重为 $1$ 的边数最多，且在所有使权重为 $1$ 的边数最大的匹配中，包含权重为 $2$ 的边数也最多，以此类推，则称该匹配为贪心匹配。

你的任务是求出在一个动态增长的图中，贪心匹配的大小（边数）。

输入格式

输入的第一行包含两个非负整数 $n$ 和 $q$ ($n \le 10^5, q \le 10^3$)：每一侧顶点的数量以及不同权重的数量。

接下来输入包含 $q$ 个块。第 $i$ 个块以一个非负整数 $m_i$ 开头：权重为 $i$ 的边的数量。接下来的 $m_i$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n$)，表示在左侧部分的顶点 $x$ 和右侧部分的顶点 $y$ 之间添加一条边。保证 $\sum_i m_i \le 2 \cdot 10^5$。

注意：两个顶点之间可能存在多条边。

输出格式

你需要在一行中输出 $q$ 个整数：分别对应权重至多为 $1$、权重至多为 $2$、……、权重至多为 $q$ 的问题的答案。

样例

样例输入 1

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

样例输出 1

1 2 2 3