#PQJ2588x15057. QOJ 2588_15057

    ID: 2840 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:JSOI 2014枚举

QOJ 2588_15057

故事背景

文艺青年 JYY 非常喜欢观看歌剧表演。JYY 知道所有演员的长相和名字,但是却对不上号,JYY 希望有一天能够知道每一个演员到底是谁。

问题描述

JSOI 歌剧团一共有 𝑁 个演员,并进行了 𝑀 次演出。所有演员由 1 到 𝑁 编号,并且第 𝑖 次演出共有 𝐾 𝑖 位演员参加。

JYY 看过所有 𝑁 个演员的照片(即知道这 𝑁 个演员的长相),也看过演员的名单(即知道这 𝑁 个演员的姓名,假设没有同名的情况),并且仔细观摩了所有的 𝑀 次演出:每次演出 JYY 都知道有哪些演员参加了本次表演并且能够分辨出他们的长相。

现在 JYY 想知道,看完这 𝑀 次演出之后,他是不是能够把所有演员的名字和长相都一一对应了呢?

输入格式

输入一行包含两个正整数 𝑁 和 𝑀 。

接下来 𝑀 行,每行首先包含一个整数 𝐾 𝑖 ,接下来 𝐾 𝑖 个不同的 1 到 𝑁 之间的整数,表示参与此次演出的演员编号。

输出格式

输出文件包含一行 𝑁 个整数,第 𝑖 个整数 𝑎 𝑖 表示编号为 𝑖 的演员在第 𝑎 𝑖 场演出之后 JYY 就可以将他的编号和长相对应起来。如果 𝑀 次演出之后 JYY 仍然不能认出这个演员,则 𝑎 𝑖 为 0 。

样例数据 样例 1 输入 5 3 3 1 2 3 3 2 3 1 2 1 3 样例 1 输出 0 3 0 0 0 样例 2 输入 4 3 1 1 1 3 1 2 样例 2 输出 1 3 2 3 样例说明

对于第一个样例,前两场演出参与人员是一样的,而第三场演出少了演员 2,所以经过对比 JYY 可以在第三场演出结束后认出演员 2。

对于第二个样例,每一场演出可以确定一个演员的长相,而 4 号演员是唯一一直没有参加过演出的。由于 JYY 一开始知道所有演员的长相,所以第三场演出后 JYY 也可以确认 4 号演员的长相。

子任务

对于 30 % 的数据满足 𝑁 , 𝑀 , ∑ 𝑖 𝐾 𝑖 ≤ 100 ;

对于 50 % 的数据满足 𝑁 , 𝑀 , ∑ 𝑖 𝐾 𝑖 ≤ 1 000 ;

对于 100 % 的数据满足 𝑁 , 𝑀 , ∑ 𝑖 𝐾 𝑖 ≤ 100 000 ;