logo AlgoBeat OnlineJudge
登录 注册

#215438. [ROI 2012 Day 2] theatre 剧院始于演员

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

翻译来源:loj #5460. 「ROI 2012 Day 2」剧院始于演员


奥林匹克参赛者来到喀山剧院观看一场演出,剧中有 位他们不认识的演员。剧院大厅悬挂着剧团所有演员的肖像,且整个剧团都参与了演出,但肖像未标注姓名。观众收到节目单,节目单中列出了每幕演出参与演员的姓氏,但未标明他们的角色。

剧迷维塔利决定弄清楚节目单中提到的每位演员的长相。为此,他在每幕演出后的幕间休息时到大厅,将肖像与看到的演员进行对照。

你需要编写一个程序,根据演员数量 和每幕演出 中参与演员的姓氏列表,确定在哪一幕演出后首次可以确定节目单中演员姓氏与肖像的对应关系。

输入格式

输入文件的第一行包含两个自然数 ,分别表示演员数量和演出幕数。

接下来的 行,每行首先是一个整数 ,表示第 幕演出的参与演员数量,随后是 个不同的自然数(不超过 ),表示参与该幕演出的演员姓氏编号。行内相邻数字以空格分隔。

输出格式

输出文件应包含一行,由 个以空格分隔的整数组成。第 个整数表示在第几幕演出后首次可以确定第 位演员与肖像的对应关系。如果到演出结束仍无法确定某位演员与肖像的对应关系,则对应位置的数字应为

样例

样例输入 1

3 3
2 1 2
2 3 2
2 1 2

样例输出 1

2 2 1

样例输入 2

5 3
3 1 2 3
3 2 3 1
2 1 3

样例输出 2

0 3 0 0 0

样例输入 3

4 3
1 1
1 3
1 2

样例输出 3

1 3 2 3

数据范围与提示

在第一个样例中,有三位演员参与了一场包含三幕的演出。第一幕有两位演员,编号为 。由于总共有三位演员,因此在第一幕结束后,可以确定编号为 的演员对应的肖像,所以输出行的第三个数字为

第二幕有两位演员,编号为 。由于只有编号为 的演员同时参与了第一幕和第二幕,因此在第二幕结束后可以确定其肖像。同时,因为总共有三幅肖像,所以在第二幕结束后也可以确定最后一张肖像对应编号为 的演员。第三幕对结果没有影响。

详细子任务附加限制及分值如下表所示:

子任务 分值 附加限制
演员数量 ,幕数
演员数量 ,幕数
演员数量 ,幕数