Ivan is a programming teacher. During the academic year, he plans to give $n$ lectures on $n$ different topics. Each topic should be used in exactly one lecture. Ivan wants to choose which topic will he explain during the $1$-st, $2$-nd, ..., $n$-th lecture — formally, he wants to choose some permutation of integers from $1$ to $n$ (let's call this permutation $q$). $q_i$ is the index of the topic Ivan will explain during the $i$-th lecture.

For each topic (except exactly one), there exists a prerequisite topic (for the topic $i$, the prerequisite topic is $p_i$). Ivan cannot give a lecture on a topic before giving a lecture on its prerequisite topic. There exists at least one valid ordering of topics according to these prerequisite constraints.

Ordering the topics correctly can help students understand the lectures better. Ivan has $k$ special pairs of topics $(x_i, y_i)$ such that he knows that the students will understand the $y_i$-th topic better if the lecture on it is conducted right after the lecture on the $x_i$-th topic. Ivan wants to satisfy the constraints on every such pair, that is, for every $i \in [1, k]$, there should exist some $j \in [1, n - 1]$ such that $q_j = x_i$ and $q_{j + 1} = y_i$.

Now Ivan wants to know if there exists an ordering of topics that satisfies all these constraints, and if at least one exists, find any of them.


-----Input-----

The first line contains two integers $n$ and $k$ ($2 \le n \le 3 \cdot 10^5$, $1 \le k \le n - 1$) — the number of topics and the number of special pairs of topics, respectively.

The second line contains $n$ integers $p_1$, $p_2$, ..., $p_n$ ($0 \le p_i \le n$), where $p_i$ is the prerequisite topic for the topic $i$ (or $p_i = 0$ if the $i$-th topic has no prerequisite topics). Exactly one of these integers is $0$. At least one ordering of topics such that for every $i$ the $p_i$-th topic is placed before the $i$-th topic exists.

Then $k$ lines follow, the $i$-th line contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$; $x_i \ne y_i$) — the topics from the $i$-th special pair. All values of $x_i$ are pairwise distinct; similarly, all valus of $y_i$ are pairwise distinct.


-----Output-----

If there is no ordering of topics meeting all the constraints, print $0$.

Otherwise, print $n$ pairwise distinct integers $q_1$, $q_2$, ..., $q_n$ ($1 \le q_i \le n$) — the ordering of topics meeting all of the constraints. If there are multiple answers, print any of them.


-----Examples-----

Input
5 2
2 3 0 5 3
1 5
5 4
Output
3 2 1 5 4
Input
5 2
2 3 0 5 3
1 5
5 1
Output
0
Input
5 1
2 3 0 5 3
4 5
Output
0
Input
5 4
2 3 0 5 3
2 1
3 5
5 2
1 4
Output
3 5 2 1 4


-----Note-----

None

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms

Sorting

Implementation

Tree algorithms

Spanning trees
Skill types: Sorting

Starter code:

Solutions:
class Node:

	def __init__(self, value):
		self.value = value
		self.next = None
		self.prev = None

	def __repr__(self):
		if not self:
			return '{}()'.format(self.__class__.__name__)
		return '{}({})'.format(self.__class__.__name__, self.value)

class LL:

	def __init__(self, iterable=None):
		self.sentinel = Node(None)
		self.sentinel.next = self.sentinel
		self.sentinel.prev = self.sentinel
		self.__len = 0
		if iterable is not None:
			self += iterable

	def get_node(self, index):
		node = sentinel = self.sentinel
		i = 0
		while i <= index:
			node = node.next
			if node == sentinel:
				break
			i += 1
		if node == sentinel:
			node = None
		return node

	def __getitem__(self, index):
		node = self.get_node(index)
		return node.value

	def __len__(self):
		return self.__len

	def __setitem__(self, index, value):
		node = self.get_node(index)
		node.value = value

	def __delitem__(self, index):
		node = self.get_node(index)
		if node:
			node.prev.next = node.next
			if node.next:
				node.next.prev = node.prev
			node.prev = None
			node.next = None
			node.value = None
			self.__len -= 1

	def __repr__(self):
		return str(self.to_list())

	def to_list(self):
		l = []
		c = self.sentinel.next
		while c != self.sentinel:
			l.append(c.value)
			c = c.next
		return l

	def append(self, value):
		sentinel = self.sentinel
		node = Node(value)
		self.insert_between(node, sentinel.prev, sentinel)

	def appendleft(self, value):
		sentinel = self.sentinel
		node = Node(value)
		self.insert_between(node, sentinel, sentinel.next)

	def insert(self, index, value):
		sentinel = self.sentinel
		new_node = Node(value)
		len_ = len(self)
		if len_ == 0:
			self.insert_between(new_node, sentinel, sentinel)
		elif index >= 0 and index < len_:
			node = self.get_node(index)
			self.insert_between(new_node, node.prev, node)
		elif index == len_:
			self.insert_between(new_node, sentinel.prev, sentinel)
		else:
			raise IndexError
		self.__len += 1

	def insert_between(self, node, left_node, right_node):
		if node and left_node and right_node:
			node.prev = left_node
			node.next = right_node
			left_node.next = node
			right_node.prev = node
		else:
			raise IndexError

	def merge_left(self, other):
		sentinel = self.sentinel
		sentinel.next.prev = other.sentinel.prev
		other.sentinel.prev.next = sentinel.next
		sentinel.next = other.sentinel.next
		sentinel.next.prev = sentinel

	def merge_right(self, other):
		sentinel = self.sentinel
		sentinel.prev.next = other.sentinel.next
		other.sentinel.next.prev = sentinel.prev
		sentinel.prev = other.sentinel.prev
		sentinel.prev.next = sentinel
import sys, io, os
Z = sys.stdin.readline
Y = lambda : map(int, Z().split())
X = lambda : print(0) or quit()
from collections import deque

def path(R):
	H = deque()
	H.append(R)
	while P[R] >= 0:
		R = P[R]
		H.append(R)
		if len(H) > 2:
			P[H.popleft()] = H[-1]
	return R
(N, k) = Y()
p = [*Y()]
K = [-1] * N
P = [-1] * (N // 2)
S = [1] * (N // 2)
ch = []
R = 0
for _ in range(k):
	(a, b) = Y()
	a -= 1
	b -= 1
	if K[a] >= 0:
		if K[b] >= 0:
			(va, vb) = (path(K[a]), path(K[b]))
			if va != vb:
				(sa, sb) = (S[va], S[vb])
				if sa > sb:
					P[vb] = va
					ch[va].merge_right(ch[vb])
					ch[vb] = 0
				else:
					P[va] = vb
					ch[vb].merge_left(ch[va])
					ch[va] = 0
					if sa == sb:
						S[vb] += 1
			else:
				X()
		else:
			va = path(K[a])
			K[b] = va
			ch[va].append(b)
	elif K[b] >= 0:
		vb = path(K[b])
		K[a] = vb
		ch[vb].appendleft(a)
	else:
		K[a] = R
		K[b] = R
		R += 1
		l = LL()
		l.append(a)
		l.append(b)
		ch.append(l)
f = [[] for i in range(N)]
x = [-1] * N
h = [0] * N
u = set()
for z in ch:
	if z != 0:
		c = z.sentinel.next
		i = 0
		while c != z.sentinel:
			x[c.value] = i
			i += 1
			c = c.next
for i in range(N):
	(a, b) = (p[i] - 1, i)
	(va, vb) = (a, b)
	if a < 0:
		z = b
		continue
	if K[a] >= 0:
		va = ch[path(K[a])][0]
	if K[b] >= 0:
		vb = ch[path(K[b])][0]
	if va == vb:
		if x[a] > x[b]:
			X()
	elif (va, vb) not in u:
		f[va].append(vb)
		h[vb] += 1
		u.add((va, vb))
q = [z]
o = []
u = set()
while q:
	v = q.pop()
	if v in u:
		X()
	u.add(v)
	if x[v] >= 0:
		o += ch[path(K[v])].to_list()
	else:
		o.append(v)
	for i in f[v]:
		h[i] -= 1
		if h[i] < 1:
			q.append(i)
if len(o) < N:
	X()
print(' '.join(map(lambda i: str(i + 1), o)))


from collections import defaultdict

def topological_sort(digraph):
	n = len(digraph)
	indegree = defaultdict(int)
	for k in digraph:
		for nxt_v in digraph[k]:
			indegree[nxt_v] += 1
	tp_order = [k for k in digraph if indegree[k] == 0]
	stack = tp_order[:]
	while stack:
		v = stack.pop()
		for nxt_v in digraph[v]:
			indegree[nxt_v] -= 1
			if indegree[nxt_v] == 0:
				stack.append(nxt_v)
				tp_order.append(nxt_v)
	return (len(tp_order) == n, tp_order)

class UF:

	def __init__(self, N):
		self.par = list(range(N))
		self.sz = [1] * N

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return False
		if self.sz[xr] < self.sz[yr]:
			(xr, yr) = (yr, xr)
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]
		return True

	def size(self, x):
		return self.sz[self.find(x)]

	def connected(self, x, y):
		return self.find(x) == self.find(y)

def main():
	(n, k) = map(int, input().split(' '))
	p = list(map(lambda x: int(x) - 1, input().split(' ')))
	pairs = {}
	uf = UF(n)
	pairs = [-1 for _ in range(n)]
	starting_points = set([i for i in range(n)])
	group_count = n
	for _ in range(k):
		(x, y) = map(int, input().split(' '))
		x -= 1
		y -= 1
		if uf.find(x) != uf.find(y):
			uf.union(x, y)
			group_count -= 1
		pairs[x] = y
		starting_points.remove(y)
	if len(starting_points) != group_count:
		print(0)
		return
	group_ordering = {}
	for sp in starting_points:
		cur_group = uf.find(sp)
		ordering = []
		vis = set()
		cur_node = sp
		while cur_node != -1:
			if cur_node in vis:
				print(0)
				return
			vis.add(cur_node)
			ordering.append(cur_node)
			cur_node = pairs[cur_node]
		group_ordering[cur_group] = ordering
	for (group_num, ordering) in group_ordering.items():
		vis = set()
		for node in ordering:
			if uf.find(p[node]) == group_num:
				if p[node] != -1 and p[node] not in vis:
					print(0)
					return
			vis.add(node)
	remap_idx = 0
	d = {}
	inverse_d = {}
	for i in range(n):
		cur_group = uf.find(i)
		if cur_group not in d:
			d[cur_group] = remap_idx
			inverse_d[remap_idx] = cur_group
			remap_idx += 1
	graph = {}
	for (child, parent) in enumerate(p):
		child_group = uf.find(child)
		if child_group not in graph:
			graph[child_group] = []
		if parent != -1:
			parent_group = uf.find(parent)
			if parent_group not in graph:
				graph[parent_group] = []
			if parent_group != child_group:
				graph[parent_group].append(child_group)
	(valid, topo_sort) = topological_sort(graph)
	if valid:
		ans = []
		for group in topo_sort:
			for node in group_ordering[group]:
				ans.append(str(node + 1))
		print(' '.join(ans))
	else:
		print(0)
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
from collections import deque
(n, k) = map(int, input().split())
P = list(map(int, input().split()))
T = [tuple(map(int, input().split())) for i in range(k)]
for i in range(n):
	if P[i] == 0:
		initial = i + 1
D = dict()
D2 = dict()
Group = [i for i in range(n + 1)]
Nodes = [1] * (n + 1)

def find(x):
	while Group[x] != x:
		x = Group[x]
	return x

def Union(x, y):
	if find(x) != find(y):
		if Nodes[find(x)] < Nodes[find(y)]:
			Nodes[find(y)] += Nodes[find(x)]
			Nodes[find(x)] = 0
			Group[find(x)] = find(y)
		else:
			Nodes[find(x)] += Nodes[find(y)]
			Nodes[find(y)] = 0
			Group[find(y)] = find(x)
for (x, y) in T:
	Union(x, y)
	if x in D:
		print(0)
		sys.exit()
	if y in D2:
		print(0)
		sys.exit()
	if y == initial:
		print(0)
		sys.exit()
	D[x] = y
	D2[y] = x
E = [set() for i in range(n + 1)]
for i in range(n):
	if P[i] == 0:
		initial = i + 1
	elif P[i] in D2 and D2[P[i]] == i + 1:
		print(0)
		sys.exit()
	else:
		E[find(P[i])].add(find(i + 1))
EDGEIN = [0] * (n + 1)
for i in range(n + 1):
	for to in E[i]:
		if find(i) == find(to):
			continue
		EDGEIN[to] += 1
Q = []
for i in range(1, n + 1):
	if find(i) != i:
		continue
	if EDGEIN[i] == 0:
		Q.append(i)
ANS = []
USE = [0] * (n + 1)
while Q:
	x = Q.pop()
	if USE[x] == 1:
		print(0)
		sys.exit()
	else:
		USE[x] = 0
		z = x
		count = 0
		while z in D2:
			z = D2[z]
			count += 1
			if count > n + 5:
				print(0)
				sys.exit()
		ANS.append(z)
		while z in D:
			if USE[D[z]] == 0:
				ANS.append(D[z])
				z = D[z]
				USE[z] = 1
			else:
				print(0)
				sys.exit()
	for to in E[x]:
		EDGEIN[to] -= 1
		if EDGEIN[to] == 0:
			Q.append(to)
if len(ANS) == n:
	print(*ANS)
else:
	print(0)


def main():
	(n, k) = map(int, input().split())
	pp = [int(a) - 1 for a in input().split()]
	chainhead = [True] * n
	follower = [None] * n
	for _ in range(k):
		(x, y) = map(int, input().split())
		if follower[x - 1]:
			print(0)
			return
		else:
			follower[x - 1] = y - 1
			chainhead[y - 1] = False
	chain = list(range(n))
	cd = [0] * n
	for i in range(n):
		if chainhead[i]:
			f = follower[i]
			d = 1
			while f != None:
				cd[f] = d
				d += 1
				chain[f] = i
				f = follower[f]
	chainparents = [[] for _ in range(n)]
	ccount = [0] * n
	for i in range(n):
		if pp[i] != -1:
			if chain[i] != chain[pp[i]]:
				chainparents[chain[i]].append(chain[pp[i]])
				ccount[chain[pp[i]]] += 1
			elif cd[pp[i]] > cd[i]:
				print(0)
				return
	s = [i for i in range(n) if chainhead[i] and ccount[i] == 0]
	l = []
	while s:
		v = s.pop()
		l.append(v)
		for p in chainparents[v]:
			ccount[p] -= 1
			if ccount[p] == 0:
				s.append(p)
	if any((ccount[i] != 0 for i in range(n))):
		print(0)
		return
	res = []
	for h in l[::-1]:
		c = h
		while c != None:
			res.append(c + 1)
			c = follower[c]
	print(' '.join(map(str, res)))
main()


from sys import stdin, gettrace
if gettrace():

	def inputi():
		return input()
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def main():
	(n, k) = map(int, input().split())
	pp = [int(a) - 1 for a in input().split()]
	chainhead = [True] * n
	follower = [None] * n
	for _ in range(k):
		(x, y) = map(int, input().split())
		if follower[x - 1]:
			print(0)
			return
		else:
			follower[x - 1] = y - 1
			chainhead[y - 1] = False
	chain = list(range(n))
	cd = [0] * n
	for i in range(n):
		if chainhead[i]:
			f = follower[i]
			d = 1
			while f != None:
				cd[f] = d
				d += 1
				chain[f] = i
				f = follower[f]
	chainparents = [[] for _ in range(n)]
	ccount = [0] * n
	for i in range(n):
		if pp[i] != -1:
			if chain[i] != chain[pp[i]]:
				chainparents[chain[i]].append(chain[pp[i]])
				ccount[chain[pp[i]]] += 1
			elif cd[pp[i]] > cd[i]:
				print(0)
				return
	s = [i for i in range(n) if chainhead[i] and ccount[i] == 0]
	l = []
	while s:
		v = s.pop()
		l.append(v)
		for p in chainparents[v]:
			ccount[p] -= 1
			if ccount[p] == 0:
				s.append(p)
	if any((ccount[i] != 0 for i in range(n))):
		print(0)
		return
	res = []
	for h in l[::-1]:
		c = h
		while c != None:
			res.append(c + 1)
			c = follower[c]
	print(' '.join(map(str, res)))
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):

	def __init__(self, file):
		self.newlines = 0
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def S():
	return input().strip()

def print_list(l):
	print(' '.join(map(str, l)))
from collections import defaultdict as dc

class DSU:

	def __init__(self, n):
		self.uf = list(range(n))
		self.rank = [1] * n

	def find(self, x):
		p = []
		while self.uf[x] != x:
			p.append(x)
			x = self.uf[x]
		for v in p:
			self.uf[v] = x
		return self.uf[x]

	def union(self, x, y):
		(px, py) = (self.find(x), self.find(y))
		if px != py:
			self.uf[py] = px
			return True
		return False
(n, k) = RL()
pre = [0] + RLL()
dsu = DSU(n + 1)
nex = [0] * (n + 1)
group = [0] * (n + 1)
rank_inner = [0] * (n + 1)
gress_group = dc(int)
edges_group = dc(list)
member = dc(list)
for _ in range(k):
	(u, v) = RL()
	if not dsu.union(u, v):
		print(0)
		exit()
	nex[u] = v
for i in range(1, n + 1):
	if group[i]:
		continue
	g = dsu.find(i)
	(u, t) = (g, 1)
	while u:
		(group[u], rank_inner[u]) = (g, t)
		member[g].append(u)
		t += 1
		u = nex[u]
for v in range(1, n + 1):
	u = pre[v]
	if u == 0:
		continue
	(gu, gv) = (group[u], group[v])
	if gu != gv:
		gress_group[gv] += 1
		edges_group[gu].append(gv)
	elif rank_inner[u] > rank_inner[v]:
		print(0)
		exit()
leaf = [g for g in member if gress_group[g] == 0]
ans = []
while leaf:
	gu = leaf.pop()
	ans += member[gu]
	for gv in edges_group[gu]:
		gress_group[gv] -= 1
		if gress_group[gv] == 0:
			leaf.append(gv)
if len(ans) < n:
	print(0)
else:
	print_list(ans)


def main():
	(n, k) = map(int, input().split())
	p = [int(x) - 1 for x in input().split()]
	isHead = [True] * n
	follower = [None] * n
	for i in range(k):
		(x, y) = map(int, input().split())
		if follower[x - 1] is not None:
			print(0)
			return
		isHead[y - 1] = False
		follower[x - 1] = y - 1
	head = [i for i in range(n)]
	depth = [0] * n
	for i in range(n):
		if isHead[i]:
			f = follower[i]
			d = 1
			while f is not None:
				head[f] = i
				depth[f] = d
				d += 1
				f = follower[f]
	mergedParents = [[] for i in range(n)]
	indegree = [0] * n
	for i in range(n):
		if p[i] != -1:
			if head[i] != head[p[i]]:
				mergedParents[head[i]].append(head[p[i]])
				indegree[head[p[i]]] += 1
			elif depth[i] < depth[p[i]]:
				print(0)
				return
	stack = [i for i in range(n) if isHead[i] and indegree[i] == 0]
	revList = []
	while stack:
		node = stack.pop()
		revList.append(node)
		for parent in mergedParents[node]:
			indegree[parent] -= 1
			if indegree[parent] == 0:
				stack.append(parent)
	if any((indegree[i] != 0 for i in range(n))):
		print(0)
		return
	for a in revList[::-1]:
		f = a
		while f is not None:
			print(f + 1, end=' ')
			f = follower[f]
main()


import sys
from collections import deque
input = sys.stdin.readline
(N, K) = map(int, input().split())
p = list(map(int, input().split()))
p = [p[i] - 1 for i in range(N)]
next = [-1 for i in range(N)]
deg = [0 for i in range(N)]
for _ in range(K):
	(x, y) = map(int, input().split())
	next[x - 1] = y - 1
	deg[y - 1] += 1
group = [-1 for i in range(N)]
deq = []
for v in range(N):
	if not deg[v]:
		deq.append(v)
		group[v] = v
deq = deque([v for v in range(N) if not deg[v]])
order = [0 for i in range(N)]
while deq:
	v = deq.popleft()
	nv = next[v]
	if nv != -1:
		deg[nv] -= 1
		if deg[nv] == 0:
			deq.append(nv)
			order[nv] = order[v] + 1
			group[nv] = group[v]
for i in range(N):
	if group[i] == -1:
		exit(print(0))
deg = [0 for i in range(N)]
out = [[] for i in range(N)]
for i in range(N):
	g = group[i]
	if p[i] == -1:
		continue
	pre = group[p[i]]
	if g != pre:
		out[pre].append(g)
		deg[g] += 1
	elif order[p[i]] > order[i]:
		exit(print(0))
deq = deque([v for v in range(N) if not deg[v]])
res = []
while deq:
	v = deq.popleft()
	res.append(v)
	for nv in out[v]:
		deg[nv] -= 1
		if not deg[nv]:
			deq.append(nv)
if len(res) != N:
	exit(print(0))
ans = []
for v in res:
	if group[v] == v:
		pos = v
		while pos != -1:
			ans.append(pos + 1)
			pos = next[pos]
print(*ans)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	from collections import deque
	input = sys.stdin.buffer.readline
	(N, K) = map(int, input().split())
	P = list(map(int, input().split()))
	nxt = [-1] * (N + 1)
	prev = [-1] * (N + 1)
	adj = [[] for _ in range(N + 1)]
	for _ in range(K):
		(x, y) = map(int, input().split())
		nxt[x] = y
		prev[y] = x
		adj[x].append(y)
	for (i, p) in enumerate(P):
		if p != 0:
			adj[p].append(i + 1)
	for v in range(1, N + 1):
		r = v
		r_list = [r]
		while prev[r] != -1:
			r = prev[r]
			r_list.append(r)
			if r == v:
				print(0)
				exit()
		for u in r_list[:-1]:
			prev[u] = r
	for v in range(1, N + 1):
		if prev[v] != -1:
			r = prev[v]
			p = P[v - 1]
			if prev[p] != r and p != r:
				adj[p].append(r)
	in_num = [0] * (N + 1)
	for v in range(1, N + 1):
		for u in adj[v]:
			in_num[u] += 1
	st = []
	for v in range(1, N + 1):
		if in_num[v] == 0:
			st.append(v)
	ans = []
	seen = [0] * (N + 1)
	while st:
		v = st.pop()
		if seen[v]:
			continue
		else:
			seen[v] = 1
		ans.append(v)
		for u in adj[v]:
			in_num[u] -= 1
			if in_num[u] == 0:
				st.append(u)
		if nxt[v] != -1:
			if in_num[nxt[v]] != 0:
				break
			st.append(nxt[v])
	if len(ans) != N:
		print(0)
	else:
		print(*ans)
main()


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def output(*args):
	sys.stdout.buffer.write(('\n'.join(map(str, args)) + '\n').encode('utf-8'))

class UnionFind(object):
	__slots__ = ['nodes']

	def __init__(self, n: int):
		self.nodes = [-1] * n

	def size(self, x: int) -> int:
		return -self.nodes[self.find(x)]

	def find(self, x: int) -> int:
		if self.nodes[x] < 0:
			return x
		else:
			self.nodes[x] = self.find(self.nodes[x])
			return self.nodes[x]

	def unite(self, x: int, y: int) -> bool:
		(root_x, root_y, nodes) = (self.find(x), self.find(y), self.nodes)
		if root_x != root_y:
			if nodes[root_x] > nodes[root_y]:
				(root_x, root_y) = (root_y, root_x)
			nodes[root_x] += nodes[root_y]
			nodes[root_y] = root_x
		return root_x != root_y

def main():
	from collections import defaultdict
	(n, k) = map(int, input().split())
	p = [0] + list(map(int, input().split()))
	sp_pair = [tuple(map(int, input().split())) for _ in range(k)]
	(indeg, outdeg) = ([0] * (n + 1), [0] * (n + 1))
	adj = [[] for _ in range(n + 1)]
	(sp_indeg, sp_outdeg) = ([0] * (n + 1), [0] * (n + 1))
	sp_adj = [[] for _ in range(n + 1)]
	uf = UnionFind(n + 1)
	for (u, v) in sp_pair:
		uf.unite(u, v)
		sp_outdeg[u] += 1
		sp_indeg[v] += 1
		sp_adj[u].append(v)
	if max(max(sp_indeg), max(sp_outdeg)) > 1:
		print(0)
		exit()
	sp_component = defaultdict(list)
	for i in range(1, n + 1):
		sp_component[uf.find(i)].append(i)
	root = -1
	for (v, u) in enumerate(p[1:], start=1):
		if u == 0:
			root = uf.find(v)
			continue
		if uf.find(u) != uf.find(v):
			(u, v) = (uf.find(u), uf.find(v))
			adj[u].append(v)
			outdeg[u] += 1
			indeg[v] += 1
		else:
			sp_adj[u].append(v)
			sp_outdeg[u] += 1
			sp_indeg[v] += 1
	stack = [root]
	ans = []
	while stack:
		v = stack.pop()
		if len(sp_component[v]) > 1:
			sv = [u for u in sp_component[v] if sp_indeg[u] == 0]
			if not sv:
				print(0)
				exit()
			stack2 = [sv[0]]
			while stack2:
				sv = stack2.pop()
				ans.append(sv)
				for dest in sp_adj[sv]:
					if sp_indeg[dest] == 0:
						continue
					sp_indeg[dest] -= 1
					if sp_indeg[dest] == 0:
						stack2.append(dest)
		else:
			ans.append(v)
		for dest in adj[v]:
			if indeg[dest] == 0:
				continue
			indeg[dest] -= 1
			if indeg[dest] == 0:
				stack.append(dest)
	if len(ans) == n:
		output(' '.join(map(str, ans)))
	else:
		print(0)
main()