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.


-----Examples-----
Input
6 2
5 3
0
0
0
2 2 1
1 4
1 5

Output
5
1 2 3 4 5 

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

Output
6
1 2 9 4 5 3 

Input
3 3
1 2 3
1 2
1 3
1 1

Output
-1



-----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.

Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal

Implementation

Starter code:

Solutions:
(n, k) = list(map(lambda x: int(x), input().split()))
m = list(map(lambda x: int(x), input().split()))
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	@bootstrap
	def DFSUtil(self, temp, v, visited):
		visited[v] = True
		for i in self.adj[v]:
			if visited[i] == False:
				yield self.DFSUtil(temp, i, visited)
		temp.append(v)
		yield temp

	def addEdge(self, v, w):
		self.adj[v].append(w)

	@bootstrap
	def isCyclicUtil(self, v, visited, recStack):
		visited[v] = True
		recStack[v] = True
		for neighbour in self.adj[v]:
			if visited[neighbour] == False:
				ans = (yield self.isCyclicUtil(neighbour, visited, recStack))
				if ans == True:
					yield True
			elif recStack[neighbour] == True:
				yield True
		recStack[v] = False
		yield False

	def isCyclic(self, nodes):
		visited = [False] * self.V
		recStack = [False] * self.V
		for node in nodes:
			if visited[node] == False:
				if self.isCyclicUtil(node, visited, recStack) == True:
					return True
		return False
G = Graph(n)
for i in range(0, n):
	x = list(map(lambda x: int(x), input().split()))
	if x[0] == 0:
		continue
	else:
		for k in range(1, x[0] + 1):
			G.addEdge(i, x[k] - 1)
visited = [False for _ in range(n)]
path = []
for subj in m:
	temp = []
	if visited[subj - 1] == False:
		G.DFSUtil(temp, subj - 1, visited)
		path.extend(temp)
if G.isCyclic([x - 1 for x in m]):
	print(-1)
else:
	print(len(path))
	for p in path:
		print(p + 1, end=' ')
	print()


line1 = input().split(' ')
n = int(line1[0])
k = int(line1[1])
main = list(map(int, input().split(' ')))
reqs = [None] * (n + 1)
for i in range(n):
	line = input().split(' ')
	if int(line[0]) == 0:
		reqs[1 + i] = []
	else:
		curr_reqs = []
		for req in line[1:]:
			curr_reqs += [int(req)]
		reqs[1 + i] = curr_reqs
res = []
to_exit = False

def traverse(main_courses):
	global res, to_exit
	roots = [False] * (n + 1)
	while main_courses and (not to_exit):
		main_to_trav = main_courses.pop()
		if reqs[main_to_trav] == None:
			continue
		stack = [main_to_trav]
		while len(stack) > 0 and (not to_exit):
			to_traverse = stack.pop()
			if reqs[to_traverse] is not None:
				childs = reqs[to_traverse]
				if len(childs) == 0:
					roots[to_traverse] = False
					res.append(to_traverse)
					reqs[to_traverse] = None
				else:
					roots[to_traverse] = True
					stack.append(to_traverse)
					for child in childs:
						if roots[child] == True:
							print(-1)
							to_exit = True
							break
					stack += childs
					reqs[to_traverse] = []
traverse(main)
if not to_exit:
	print(len(res))
	print(' '.join(map(str, res)))


import sys
sys.setrecursionlimit(10 ** 8)
cycle = False

def DFS(i, graph, result, visited):
	global cycle
	stack = [i]
	while len(stack) != 0:
		u = stack[-1]
		visited[u] = 1
		if len(graph[u]) != 0:
			v = graph[u].pop()
			if visited[v] == 1:
				cycle = True
				return
			if visited[v] == 2:
				continue
			stack.append(v)
			visited[u] = 1
		else:
			result.append(u)
			stack.pop()
			visited[u] = 2

def TopoSort(graph, result):
	for i in range(m):
		if not visited[requiredCourse[i]]:
			DFS(requiredCourse[i], graph, result, visited)
	return result
(n, m) = map(int, input().split())
requiredCourse = list(map(int, input().split()))
graph = [[] for i in range(n + 1)]
result = []
visited = [False for i in range(n + 1)]
for i in range(1, n + 1):
	tmp = list(map(int, input().split()))
	if tmp[0] == 0:
		continue
	for j in range(1, tmp[0] + 1):
		graph[i].append(tmp[j])
res = TopoSort(graph, result)
if cycle == True:
	print(-1)
else:
	print(len(res))
	for i in res:
		print(i, end=' ')


import sys
flag = True
sys.setrecursionlimit(2000000000)
c = []
st = []
cur_adj = []

def topo(s):
	global c, st, flag
	stack = [s]
	while stack:
		s = stack[-1]
		c[s] = 1
		if cur_adj[s] < len(adjli[s]):
			cur = adjli[s][cur_adj[s]]
			if c[cur] == 0:
				stack.append(cur)
			if c[cur] == 1:
				flag = False
			cur_adj[s] += 1
		else:
			c[s] = 2
			st.append(str(s))
			del stack[-1]
try:
	(n, k) = map(int, input().split(' '))
	main = list(map(int, input().split(' ')))
	depen = []
	for i in range(n):
		depen.append(list(map(int, input().split(' ')))[1:])
		c.append(0)
		cur_adj.append(0)
	c.append(0)
	cur_adj.append(0)
	adjli = []
	adjli.append(main)
	for i in range(len(depen)):
		adjli.append(depen[i])
	topo(0)
	st.pop(-1)
	if flag:
		print(len(st))
		print(' '.join(st))
	else:
		print(-1)
except Exception as e:
	print(e, 'error')


class Course:

	def __init__(self, reqs, number):
		self.reqs = list(map(int, reqs.split()[1:]))
		self.available = False
		self.in_stack = False
		self.number = number
(n, k) = list(map(int, input().split()))
requirements = list(map(int, input().split()))
courses = {}
answer = ''
for i in range(n):
	courses[i + 1] = Course(input(), i + 1)
for i in range(len(requirements)):
	requirements[i] = courses[requirements[i]]
while requirements:
	data = {}
	course = requirements.pop()
	if not course.available:
		requirements.append(course)
		done = True
		for c in course.reqs:
			c = courses[c]
			if not c.available:
				requirements.append(c)
				done = False
		if done:
			answer += ' ' + str(course.number)
			course.available = True
		else:
			if course.in_stack:
				print(-1)
				break
			course.in_stack = True
else:
	print(answer.count(' '))
	print(answer[1:])


from sys import *
f = lambda : list(map(int, stdin.readline().split()))

class T:

	def __init__(self, i):
		(self.i, self.t) = (i, f()[1:])
		self.a = self.q = 0
(n, k) = f()
d = f()
p = [None] + [T(i + 1) for i in range(n)]
s = []
while d:
	x = p[d.pop()]
	if x.a:
		continue
	d.append(x.i)
	q = 1
	for i in x.t:
		y = p[i]
		if y.a:
			continue
		d.append(y.i)
		q = 0
	if q:
		s.append(x.i)
		x.a = 1
	elif x.q:
		print(-1)
		exit()
	else:
		x.q = 1
print(len(s), *s)


import collections as col
import itertools as its
import sys
import operator
from copy import copy, deepcopy

class Solver:

	def __init__(self):
		pass

	def solve(self):
		(n, k) = map(int, input().split())
		q = list(map(lambda x: int(x) - 1, input().split()))
		used = [False] * n
		for e in q:
			used[e] = True
		edges = [[] for _ in range(n)]
		redges = [[] for _ in range(n)]
		for i in range(n):
			l = list(map(lambda x: int(x) - 1, input().split()))[1:]
			edges[i] = l
			for e in l:
				redges[e].append(i)
		degs = [len(edges[i]) for i in range(n)]
		d = 0
		while d < len(q):
			v = q[d]
			d += 1
			for e in edges[v]:
				if not used[e]:
					used[e] = True
					q.append(e)
		q = q[::-1]
		nq = []
		for v in q:
			if degs[v] == 0:
				nq.append(v)
		d = 0
		while d < len(nq):
			v = nq[d]
			d += 1
			for e in redges[v]:
				if not used[e]:
					continue
				degs[e] -= 1
				if degs[e] == 0:
					nq.append(e)
		if len(q) != len(nq):
			print(-1)
			return
		print(len(nq))
		print(' '.join(map(lambda x: str(x + 1), nq)))
s = Solver()
s.solve()


import sys

def main():
	(n, k) = map(int, sys.stdin.readline().split())
	courses = list(map(int, sys.stdin.readline().split()))
	courses = [x - 1 for x in courses]
	visited = [False] * n
	used = [False] * n
	ans = []
	t = []
	for i in range(n):
		temp = list(map(int, sys.stdin.readline().split()))
		temp = [x - 1 for x in temp]
		t.append(temp[1:])
	for i in range(k):
		c = courses[i]
		if used[c]:
			continue
		q = [c]
		visited[c] = True
		while len(q) > 0:
			cur = q[-1]
			if len(t[cur]) != 0:
				s = t[cur].pop()
				if visited[s] and (not used[s]):
					print(-1)
					return
				if used[s]:
					continue
				q.append(s)
				visited[s] = True
			else:
				ans.append(cur)
				q.pop()
				used[cur] = True
	ans = [str(x + 1) for x in ans]
	print(len(ans))
	print(' '.join(ans))
main()


f = lambda : map(int, input().split())
g = lambda : [[] for x in range(n)]
(n, k) = f()
n += 1
(s, p) = ([], list(f()))
(c, d) = ([0] * n, [0] * n)
(u, v) = (g(), g())
for x in range(1, n):
	t = list(f())
	m = t.pop(0)
	if m:
		c[x] = m
		v[x] = t
		for y in t:
			u[y].append(x)
	else:
		s.append(x)
		d[x] = 1
while s:
	x = s.pop()
	for y in u[x]:
		c[y] -= 1
		d[y] = max(d[y], d[x] + 1)
		if c[y] == 0:
			s.append(y)
if any((c[x] for x in p)):
	print(-1)
	exit()
q = [0] * n
while p:
	x = p.pop()
	if q[x] == 0:
		p += v[x]
		q[x] = 1
p = sorted(((d[x], x) for x in range(n) if q[x]))
print(len(p))
for (d, x) in p:
	print(x)


def dfs(start_node, edges, colors, result):
	stack = [start_node]
	while stack:
		current_node = stack[-1]
		if colors[current_node] == 2:
			stack.pop()
			continue
		colors[current_node] = 1
		children = edges[current_node]
		if not children:
			colors[current_node] = 2
			result.append(stack.pop())
		else:
			child = children.pop()
			if colors[child] == 1:
				return False
			stack.append(child)
	return True

def find_courses_sequence(member_of_node, find_nodes, edges):
	colors = [0] * member_of_node
	result = []
	for node in find_nodes:
		if not dfs(node, edges, colors, result):
			return []
	return result

def __starting_point():
	(n, k) = map(int, input().split())
	main_courses = [int(c) - 1 for c in input().split()]
	courses = dict()
	for index in range(n):
		courses[index] = [int(d) - 1 for d in input().split()[1:]]
	result = find_courses_sequence(n, main_courses, courses)
	if result:
		print(len(result))
		for v in result:
			print(v + 1, end=' ')
	else:
		print(-1)
__starting_point()


(n, k) = map(int, input().split())
K = set(list(map(int, input().split())))
g = {}
rg = {}
deg = {}

def push_d(deg, u, val):
	if u not in deg:
		deg[u] = 0
	deg[u] += val

def push_g(g, u, v):
	if u not in g:
		g[u] = []
	g[u].append(v)
for u in range(1, n + 1):
	list_v = list(map(int, input().split()))[1:]
	deg[u] = 0
	for v in list_v:
		push_d(deg, u, 1)
		push_g(g, v, u)
		push_g(rg, u, v)
S = [x for x in K]
used = [0] * (n + 1)
i = 0
while i < len(S):
	u = S[i]
	if u in rg:
		for v in rg[u]:
			if used[v] == 0:
				used[v] = 1
				S.append(v)
	i += 1
S = {x: 1 for x in S}
deg0 = [x for x in S if deg[x] == 0]
ans = []

def process(g, deg, deg0, u):
	if u in g:
		for v in g[u]:
			if v in S:
				push_d(deg, v, -1)
				if deg[v] == 0:
					deg0.append(v)
while len(deg0) > 0 and len(K) > 0:
	u = deg0.pop()
	ans.append(u)
	if u in K:
		K.remove(u)
	process(g, deg, deg0, u)
if len(K) > 0:
	print(-1)
else:
	print(len(ans))
	print(' '.join([str(x) for x in ans]))


f = lambda : map(int, input().split())
g = lambda : [int(q) - 1 for q in f()]

class T:

	def __init__(s, i):
		(s.i, s.t) = (i, g()[1:])
		s.a = s.q = 0
(n, k) = f()
d = g()
p = [T(i) for i in range(n)]
s = []
while d:
	x = p[d.pop()]
	if x.a:
		continue
	d.append(x.i)
	q = 1
	for i in x.t:
		y = p[i]
		if y.a:
			continue
		d.append(y.i)
		q = 0
	if q:
		s.append(x.i + 1)
		x.a = 1
	elif x.q:
		print(-1)
		exit()
	else:
		x.q = 1
print(len(s), *s)