流行病学调查 - 题目

2020年，一种新型传染病流行，UCPC国的疾病管理本部正在进行流行病学调查。UCPC国共有 $N$ 名居民，居民编号分别为 $1, 2, \dots, N$。

疾病管理本部已掌握了至今为止发生的 $M$ 次聚会信息。每次聚会有 $k$ 人参加，参加者的居民编号分别为 $a_1, a_2, \dots, a_k$。

由于该传染病仅在密切接触的封闭空间内传播，因此它必然只在聚会中传播。传染病的传播规则如下：

疾病管理本部希望利用所掌握的资料预测初始感染者。给定聚会信息以及 $M$ 次聚会结束后人们的感染情况，请编写一个程序，逆向追踪在第一次聚会之前就已经感染的人。假设除上述规则外，不存在其他传染途径，且传染病不会自愈。

第一行包含人数 $N$ 和聚会次数 $M$ ($2 \le N \le 100\,000, 1 \le M \le 100\,000$)。

从第二行开始的 $M$ 行，按时间顺序给出聚会信息。每行包含参加该聚会的人数 $k$ ($2 \le k \le N$) 以及参加者的居民编号 $a_i$ ($1 \le a_i \le N, a_i \neq a_j$)。不存在多个聚会同时进行的情况。

最后一行给出 $N$ 名居民的感染信息。如果最后一次聚会结束后，居民编号为 $i$ 的人已感染传染病，则给出 $1$，否则给出 $0$。请注意，可能存在无人感染的情况。

所有 $k$ 的总和不超过 $1\,000\,000$。

如果无法逆向追踪出第一次聚会前的感染者，则输出 NO。

否则，第一行输出 YES，第二行输出 $N$ 个用空格分隔的整数，表示感染信息。其中第 $i$ 个数表示居民编号为 $i$ 的人在第一次聚会开始前是否已感染：若已感染则为 $1$，否则为 $0$。如果存在多种可能的感染状态，输出其中任意一种即可。

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

YES
0 0 0 1 1 1 1

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

NO

QOJ.ac