← 返回题目列表

Codeforces · 1167/C

C. 新闻发布

中文机器翻译题面 查看原题

在某些社交网络中,有 $$$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$$$ 不同的整数,表示属于第 $$$i$$$ 组的用户。

保证 $$$\sum \limits_{i = 1}^{m} k_i \le 5 \cdot 10^5$$$。

输出

打印 $$$n$$$ 整数。第 $$$i$$$ 个整数应该等于用户 $$$i$$$ 开始分发新闻时知道该新闻的用户数量。

示例

输入 #1

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

输出 #1

4 4 1 4 4 2 2