← 返回题目列表

Codeforces · 770/C

C. BSU 在线课程

中文机器翻译题面 查看原题

现在您可以在伯兰州立大学参加在线课程了! Polycarp 需要通过他专业的 k 个主要在线课程才能获得文凭。该通道总共有 n 门课程可供选择。

在线课程的依赖性使情况变得复杂,对于每门课程都有一个在开始该在线课程之前必须通过的列表(该列表可以为空,这意味着没有限制)。

帮助波利卡普通过最少数量的课程即可获得专业(即通过所有主要和必修课程)。编写一个打印课程顺序的程序。

Polycarp 始终如一地通过课程,他在完成上一门课程后开始下一门课程。每门课程不能多次通过。

输入

第一行包含n和k(1≤k≤n≤105)——Polycarp专业的在线课程数量和主要课程数量。

第二行包含 k 个从 1 到 n 的不同整数——Polycarp 专业的主要在线课程的数量。

接下来有 ​​n 行,每行描述下一门课程:其中第 i 行对应于课程 i。每行从整数 ti (0 ≤ ti ≤ n - 1) 开始——第 i 行所依赖的课程数。然后是从 1 到 n 的 ti 个不同整数的序列——随机顺序的课程数量,第 i 个取决于它。保证任何课程都不能依赖自身。

保证所有值 ti 的总和不超过 105。

输出

如果没有获得专长的方法,则打印-1。

否则,在第一行打印整数 m — 获得专业所需通过的在线课程的最小数量。在第二行中打印 m 个不同的整数 - 按照通过的时间顺序需要通过的课程数。如果有多个答案,则可以打印其中任何一个。

示例

输入 #1

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

输出 #1

5
1 2 3 4 5

输入 #2

9 3
3 9 5
0
0
3 9 4 5
0
0
1 8
1 6
1 2
2 1 2

输出 #2

6
1 2 9 4 5 3

输入 #3

3 3
1 2 3
1 2
1 3
1 1

输出 #3

-1

注意

第一次考试时,先选1、2号课程,然后选4号课程,然后选5号课程,这是主课。之后你只需要选修第3门课程,这是最后一个未通过的主菜。