CF1463E Plan of Lectures

Ivan 是一名编程教师。在学年期间，他计划讲授 $n$ 个不同主题的 $n$ 节课。每个主题只能在一节课中被讲授一次。Ivan 想要决定在第 $1$ 节、第 $2$ 节，……，第 $n$ 节课上讲授哪个主题——形式化地说，他想选择 $1$ 到 $n$ 的某个排列（记为 $q$）。$q_i$ 表示 Ivan 会在第 $i$ 节课讲授的主题编号。 对于每个主题（恰好有一个主题除外），都存在一个先修主题（对于第 $i$ 个主题，其先修主题为 $p_i$）。Ivan 不能在讲授某个主题之前讲授它的先修主题。保证至少存在一种满足这些先修关系的主题顺序。 正确地安排主题顺序有助于学生更好地理解课程。Ivan 有 $k$ 对特殊主题 $(x_i, y_i)$，他知道如果在讲授 $x_i$ 主题后紧接着讲授 $y_i$ 主题，学生会更好地理解 $y_i$ 主题。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, \ldots, p_n$（$0 \le p_i \le n$），其中 $p_i$ 表示第 $i$ 个主题的先修主题编号（如果第 $i$ 个主题没有先修主题，则 $p_i = 0$）。恰好有一个 $p_i = 0$。保证至少存在一种主题顺序，使得对于每个 $i$，$p_i$ 主题在 $i$ 主题之前。 接下来 $k$ 行，每行包含两个整数 $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, \ldots, q_n$（$1 \le q_i \le n$），表示满足所有约束条件的主题顺序。如果有多种答案，输出任意一种即可。

由 ChatGPT 4.1 翻译