C. 消息传播

每个测试的时间限制：$2$ 秒
内存限制：$256$ 兆字节

在某个社交网络中，有 $n$ 个用户，他们在 $m$ 个朋友群组中进行交流。我们来分析一下新闻在用户之间传播的过程。

最初，某个用户 $x$ 从某个来源收到新闻。然后他将新闻发送给其朋友（两个用户是朋友，如果至少存在一个群组，使得两人都属于该群组）。朋友继续将新闻发送给他们的朋友，依此类推。当不存在一对朋友使得一人知道新闻而另一人不知道时，传播过程结束。

对于每个用户 $x$，你需要确定：如果初始只有用户 $x$ 开始传播新闻，最终会有多少用户知道新闻。

输入
第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 5 \cdot 10^5$）—— 分别是用户的数量和朋友群组的数量。

接下来 $m$ 行，每行描述一个朋友群组。
第 $i$ 行以整数 $k_i$（$0 \le k_i \le n$）开头 —— 第 $i$ 组中的用户数量。
然后跟着 $k_i$ 个互不相同的整数，表示属于该组的用户编号。

数据保证 $\sum_{i=1}^{m} k_i \le 5 \cdot 10^5$。

输出
输出 $n$ 个整数。
第 $i$ 个整数应该等于：如果用户 $i$ 开始传播新闻，最终知道新闻的用户数量。

示例

输入

7 5
3 2 5 4
0
2 1 2
1 1
2 6 7

输出

4 4 1 4 4 2 2