课程安排(Plan of Lectures)

题目描述

Ivan 是编程老师，一学年要讲 $n$ 节不同主题的课。每节课恰好讲一个主题、每个主题恰好讲一次。他需要安排第 $1,2,\dots,n$ 节课分别讲哪个主题，即给出一个 $1\sim n$ 的排列 $q$，其中 $q_i$ 表示第 $i$ 节课讲的主题编号。

除恰好一个主题外，每个主题 $i$ 都有先修主题 $p_i$（$p_i=0$ 表示无先修）。主题必须在其先修主题之后才能讲。题目保证至少存在一种满足先修约束的安排。

此外有 $k$ 个"特殊主题对" $(x_i, y_i)$：若 $y_i$ 紧接在 $x_i$ 之后讲（即存在 $j$ 使 $q_j=x_i$ 且 $q_{j+1}=y_i$），学生理解更好，要求这 $k$ 个特殊对全部满足。

问是否存在满足所有约束的安排；若存在，输出任意一个合法排列。

输入格式

第一行两个整数 $n, k\ (2\le n\le 3\cdot 10^5,\ 1\le k\le n-1)$。 第二行 $n$ 个整数 $p_1,\dots,p_n\ (0\le p_i\le n)$，$p_i$ 是 $i$ 的先修主题（$0$ 表示无）。恰好有一个为 $0$，且至少存在一种合法先修顺序。 接下来 $k$ 行，每行 $x_i, y_i\ (1\le x_i,y_i\le n,\ x_i\ne y_i)$ — 特殊对。所有 $x_i$ 互不相同，所有 $y_i$ 互不相同。

输出格式

若不存在合法安排，输出 0；否则输出 $n$ 个互不相同的整数 $q_1,\dots,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

数据范围

$2\le n\le 3\cdot 10^5$；$1\le k\le n-1$。

知识点与难度

本题涉及的知识点从属于 GESP 七级，难度等级：⭐⭐⭐

测试点分布