A5412 | $News Distribution$

时间限制3s

内存限制256MB

通过 / 提交0/0

题目描述

在某个社交网络中，有 $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

输出 #1

4 4 1 4 4 2 2

C++ 编辑器

输入

输出