#CF1167C. 传下去!

传下去!

CF1167C News Distribution

题目描述

在某个社交网络中,有 nn 个用户在 mm 个好友群中互相交流。现在我们来分析一则新闻在用户之间传播的过程。

最初,某个用户 xx 从某个渠道获得了这则新闻。然后他会把新闻发送给他的好友(如果两个用户至少在一个群组中都在,则他们是好友)。好友们会继续将新闻发送给他们的好友,如此反复。这个过程会一直持续,直到不存在这样的一对好友:其中一人已经知道新闻,而另一人还不知道。

对于每个用户 xx,你需要确定:如果最初只有用户 xx 开始传播新闻,最终会有多少用户知道这则新闻。

输入格式

第一行包含两个整数 nn 和 mm(1≤n,m≤5⋅1051 \le n, m \le 5 \cdot 10^5),分别表示用户数和好友群数。

接下来有 mm 行,每行描述一个好友群。第 ii 行以整数 kik_i(0≤ki≤n0 \le k_i \le n)开头,表示第 ii 个群组中的用户数。接下来有 kik_i 个互不相同的整数,表示属于第 ii 个群组的用户编号。

保证 ∑i=1mki≤5⋅105 \sum\limits_{i=1}^{m} k_i \le 5 \cdot 10^5 。

输出格式

输出 nn 个整数,第 ii 个整数表示如果用户 ii 最先开始传播新闻,最终会有多少用户知道这则新闻。

输入输出样例 #1

输入 #1

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

输出 #1

4 4 1 4 4 2 2 

说明/提示

由 ChatGPT 4.1 翻译