#CW53. 零食分发(snack)

零食分发(snack)

题目描述

有 NN 名学生和 NN 份零食,学生与零食都编号为 1,2,…,N1, 2, \dots, N。第 ii 名学生喜欢 CiC_i 份零食,编号为 Ai,1,Ai,2,…,Ai,CiA_{i,1}, A_{i,2}, \dots, A_{i,C_i}。每名学生至少喜欢一份零食。

开始时每种零食各有一份。你可以安排学生进入房间的顺序。学生进入后会拿走房间内仍然存在且自己喜欢的所有零食;如果没有喜欢的零食,则什么也不拿。请判断是否存在一个顺序,使每名学生恰好拿走一份零食,并在存在时输出任意一个这样的顺序。

输入格式

从 snack.in 文件读入数据。

第一行包含整数 NN。接下来 NN 行描述学生 ii 的喜好:先给出整数 CiC_i,再给出 CiC_i 个两两不同的整数 Ai,1,Ai,2,…,Ai,CiA_{i,1}, A_{i,2}, \dots, A_{i,C_i}。

输出格式

输出到 snack.out 文件。

若不存在可行顺序,输出 -1。否则输出 NN 个整数 P1,P2,…,PNP_1, P_2, \dots, P_N,表示学生进入房间的顺序。任意可行顺序均可接受。

样例 1 输入

3
2 1 2
2 2 3
1 2

样例 1 输出

3 1 2

样例 2 输入

2
2 1 2
2 1 2

样例 2 输出

-1

样例 3 输入

4
1 3
1 2
3 4 2 3
2 1 2

样例 3 输出

1 2 3 4

数据范围

所有输入数均为整数。满足 1≤N≤200 0001 \le N \le 200\,000,1≤Ci≤N1 \le C_i \le N,C1+C2+⋯+CN≤500 000C_1 + C_2 + \dots + C_N \le 500\,000,1≤Ai,j≤N1 \le A_{i,j} \le N,且同一行的喜好编号两两不同。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

本题答案不唯一,采用特殊判定(SPJ):输出任意一个可行顺序均可。

子任务 分值 测试点 附加条件
1 6 1∼21\sim 2 对所有 ii 有 Ci=1C_i = 1
2 11 3∼43\sim 4 若存在可行顺序,则编号顺序 1,2,…,N1, 2, \dots, N 也可行
3 8 5∼65\sim 6 N≤5N \le 5
4 12 7∼87\sim 8 N≤18N \le 18
5 18 9∼119\sim 11 N≤300N \le 300
6 20 12∼1512\sim 15 N≤5000N \le 5000
7 25 16∼2016\sim 20 无额外限制