Ivan 是一名编程老师。在学年期间,他计划就不同主题进行 $$$n$$$ 讲座。每个主题都应该在一个讲座中使用。 Ivan 想要选择在 $$$1$$$-st、$$$2$$$-nd、...、$$$n$$$-th 讲座中解释哪个主题 - 正式地,他想要选择从 $$$1$$$ 到 $$$n$$$ 的整数排列(我们称此排列为 $$$q$$$)。 $$$q_i$$$ 是 Ivan 将在第 $$$i$$$ 次讲座中解释的主题索引。
对于每个主题(除了一个),都存在一个先决主题(对于主题 $$$i$$$,先决主题是 $$$p_i$$$)。在就某个主题进行演讲之前,伊万不能就该主题进行演讲。根据这些先决条件约束,至少存在一种有效的主题排序。
正确排列主题可以帮助学生更好地理解讲座。 Ivan 有 $$$k$$$ 特殊主题对 $$$(x_i, y_i)$$$,这样他知道如果在第 $$$x_i$$$-th 主题讲座之后立即进行该主题的讲座,学生会更好地理解第 $$$y_i$$$-th 主题。 Ivan 希望满足每个这样的对的约束,即对于每个 $$$i \in [1, k]$$$,应该存在一些 $$$j \in [1, n - 1]$$$ 使得 $$$q_j = x_i$$$ 和 $$$q_{j + 1} = y_i$$$。
现在 Ivan 想知道是否存在满足所有这些约束的主题排序,如果至少存在一个,则找到其中任何一个。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$1 \le k \le n - 1$$$) — 分别是主题的数量和特殊主题对的数量。
第二行包含 $$$n$$$ 整数 $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$ ($$$0 \le p_i \le n$$$),其中 $$$p_i$$$ 是主题 $$$i$$$ 的先决主题(或者 $$$p_i = 0$$$,如果第 $$$i$$$ 个主题没有必备主题)。这些整数之一就是 $$$0$$$。至少有一种主题排序,使得对于每个 $$$i$$$,第 $$$p_i$$$ 个主题位于第 $$$i$$$ 个主题之前。
接下来是 $$$k$$$ 行,第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — 来自第 $$$i$$$ 特殊对的主题。 $$$x_i$$$ 的所有值都是成对不同的;类似地,$$$y_i$$$ 的所有值都是成对不同的。
输出
如果没有满足所有约束的主题排序,则打印 $$$0$$$。
否则,打印 $$$n$$$ 成对不同的整数 $$$q_1$$$, $$$q_2$$$, ..., $$$q_n$$$ ($$$1 \le q_i \le n$$$) — 满足所有约束的主题的排序。如果有多个答案,请打印其中任何一个。
示例
输入 #1
5 2 2 3 0 5 3 1 5 5 4
输出 #1
3 2 1 5 4
输入 #2
5 2 2 3 0 5 3 1 5 5 1
输出 #2
0
输入 #3
5 1 2 3 0 5 3 4 5
输出 #3
0
输入#4
5 4 2 3 0 5 3 2 1 3 5 5 2 1 4
输出#4
3 5 2 1 4