VK Cup 2017 - Qualification 2
C
Online Courses In BSU
Codeforces
1500
原题
← BD →
翻译中…

Now you can take online courses in the Berland State University! Polycarp needs to pass $*k*$ main online courses of his specialty to get a diploma. In total $*n*$ courses are availiable for the passage.

翻译中…

The situation is complicated by the dependence of online courses, for each course there is a list of those that must be passed before starting this online course (the list can be empty, it means that there is no limitation).

翻译中…

Help Polycarp to pass the least number of courses in total to get the specialty (it means to pass all main and necessary courses). Write a program which prints the order of courses.

翻译中…

Polycarp passes courses consistently, he starts the next course when he finishes the previous one. Each course can't be passed more than once.

翻译中…

Input

翻译中…

The first line contains $*n*$ and $*k*$ ($1 ≤ *k* ≤ *n* ≤ 10^{5}$) — the number of online-courses and the number of main courses of Polycarp's specialty.

翻译中…

The second line contains $*k*$ distinct integers from $1$ to $*n*$ — numbers of main online-courses of Polycarp's specialty.

翻译中…

Then $*n*$ lines follow, each of them describes the next course: the $*i*$-th of them corresponds to the course $*i*$. Each line starts from the integer $*t*_{*i*}$ ($0 ≤ *t*_{*i*} ≤ *n* - 1$) — the number of courses on which the $*i*$-th depends. Then there follows the sequence of $*t*_{*i*}$ distinct integers from $1$ to $*n*$ — numbers of courses in random order, on which the $*i*$-th depends. It is guaranteed that no course can depend on itself.

翻译中…

It is guaranteed that the sum of all values $*t*_{*i*}$ doesn't exceed $10^{5}$.

翻译中…

Output

翻译中…

Print -1, if there is no the way to get a specialty.

翻译中…

Otherwise, in the first line print the integer $*m*$ — the minimum number of online-courses which it is necessary to pass to get a specialty. In the second line print $*m*$ distinct integers — numbers of courses which it is necessary to pass in the chronological order of their passage. If there are several answers it is allowed to print any of them.

翻译中…

Note

翻译中…

In the first test firstly you can take courses number $1$ and $2$, after that you can take the course number $4$, then you can take the course number $5$, which is the main. After that you have to take only the course number $3$, which is the last not passed main course.

翻译中…

样例

Input #1
6 2
5 3
0
0
0
2 2 1
1 4
1 5
Output #1
5
1 2 3 4 5
InputCopy OutputCopy
Input #2
9 3
3 9 5
0
0
3 9 4 5
0
0
1 8
1 6
1 2
2 1 2
Output #2
6
1 2 9 4 5 3
InputCopy OutputCopy
Input #3
3 3
1 2 3
1 2
1 3
1 1
Output #3
-1
InputCopy OutputCopy
题目信息
题号
770C
时间限制
2 s
内存限制
256 MB
标签
*special
DFS 及类似
图论
模拟

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。