← 返回题目列表

Codeforces · 1463/E

E. 讲座计划

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

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