← 返回题目列表

AtCoder · pakencamp_2020_day2_d

D. 动物表演

中文机器翻译题面 查看原题
配点 : 500 点

問題文

在2020年科学技术研讨会的集训中,作为娱乐活动的一部分,N 人的 1\ldots N 被邀请来 1 每次依次让

人 i 是 A_i 种类的动物 a_{i,1},\ a_{i,2},\ldots,\ a_{i,{A_i}} 来进行表演。这里,动物的种类是 1 以上 5×10^5 用以下整数表示。

顺便说一下,在进行animarusushio时,需要确保对动物有过敏的人安全。对参与表演的人进行了问卷调查,发现了以下事实。

  • 人 i 是 B_i 种类的动物 b_{i,1},\ b_{i,2},\ldots,\ b_{i,B_i} 对…有过敏。

人 i 是一种动物 如果一个人对 X 过敏 i 以前也有人做过表演 1 人或动物 使用 X 可能会引起过敏反应。确定是否存在不会引起所有人过敏的节目顺序,如果是,请选择其中之一。 1 请输出一个。

保证所有人都不对表演中使用的动物过敏。


制約

  • 1\leq N\leq2×10^5
  • 1\leq A_i,\ B_i
  • 1\leq \sum A_i\leq5×10^5
  • 1\leq \sum B_i\leq5×10^5
  • 1\leq a_{i,j}\leq5×10^5
  • 1\leq b_{i,j}\leq5×10^5
  • a_{i,j}≠a_{i,k}\ (j≠k)
  • b_{i,j}≠b_{i,k}\ (j≠k)
  • a_{i,j}≠b_{i,k}
  • 所有输入均为整数

小課題

  1. (50 点) N\leq8,\ \sum A_i\leq100,\ \sum B_i\leq100,\ a_{i,j}\leq100,\ b_{i,j}\leq100
  2. (100 点) N\leq9,\ \sum A_i\leq2000,\ \sum B_i\leq2000,\ a_{i,j}\leq2000,\ b_{i,j}\leq2000
  3. (100 点) N\leq1000,\ \sum A_i\leq2000,\ \sum B_i\leq2000,\ a_{i,j}\leq2000,\ b_{i,j}\leq2000
  4. (250 点) 没有其他否定。

入力

输入是按以下格式从标准输入给出的。

\(N\)
\(A_1\)
\(a_{1,1}\) \(a_{1,2}\) \(\ldots\) \(a_{1,A_1}\)
\(B_1\)
\(b_{1,1}\) \(b_{1,2}\) \(\ldots\) \(b_{1,B_1}\)
\(A_2\)
\(a_{2,1}\) \(a_{2,2}\) \(\ldots\) \(a_{2,A_2}\)
\(B_2\)
\(b_{2,1}\) \(b_{2,2}\) \(\ldots\) \(b_{2,B_2}\)
\(︙\)
\(A_N\)
\(a_{N,1}\) \(a_{N,2}\) \(\ldots\) \(a_{N,A_N}\)
\(B_N\)
\(b_{N,1}\) \(b_{N,2}\) \(\ldots\) \(b_{N,B_N}\)

出力

如果有满足条件的演出订单,i 第人 正如 P_i 上演的 i 按升序排列 请输出 P_i ,以空格分隔。如果没有订单 请输出 -1 。

如果法官忘记末尾的换行符或末尾有多余的空格,则答案将不正确。请小心。

入力例1

2
2
1 2
1
3
2
1 3
1
4

出力例1

1 2

如果颠倒显示顺序, 它可能引起对 1 是一种动物 如果一个人对 3 的过敏反应。

此示例满足所有子任务约束。

入力例2

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

出力例2

-1

无论你按什么顺序表演,都会有人产生过敏反应。

此示例满足所有子任务约束。

入力例3

3
3
1 3 4
2
2 5
2
1 8
2
9 7
2
3 8
2
1 4

出力例3

3 2 1

此示例满足所有子任务约束。

作者: 企鹅人