CF883B Berland Army

贝尔兰军队有 $n$ 名士兵。其中一些人已经向其他士兵下达了命令。现给出 $m$ 对数对 $(x_{i}, y_{i})$，表示士兵 $x_{i}$ 向士兵 $y_{i}$ 下达了第 $i$ 条命令。 现在是改革的时候了！贝尔兰国防部准备在军队中引入军衔制度。每名士兵都要被分配一个军衔——这是一个介于 $1$ 到 $k$ 之间的整数。一部分士兵已经拥有了军衔，剩下的士兵需要尽快被分配军衔。 请你帮助国防部给剩下的士兵分配军衔，要求满足以下条件： - 对于每一条命令，发出命令的士兵（$x_{i}$）的军衔严格高于接受命令的士兵（$y_{i}$）； - 对于所有 $1$ 到 $k$ 的军衔，每一种军衔至少要有一名士兵拥有。

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n \leq 2 \cdot 10^{5}$，$0 \leq m \leq 2 \cdot 10^{5}$，$1 \leq k \leq 2 \cdot 10^{5}$），分别表示贝尔兰军队的人数、命令数以及军衔数。 第二行包含 $n$ 个整数 $r_1, r_2, \ldots, r_n$，其中 $r_i > 0$ 表示第 $i$ 位士兵已经被分配军衔（此时 $1 \leq r_i \leq k$），$r_i = 0$ 表示第 $i$ 位士兵尚未分配军衔。 接下来 $m$ 行，每行两个整数 $x_i, y_i$（$1 \leq x_i, y_i \leq n$，$x_i \ne y_i$），表示第 $i$ 条命令由士兵 $x_i$ 下达给士兵 $y_i$。对于同一对 $(x, y)$，可能有多条命令。

输出 $n$ 个整数，第 $i$ 个数表示第 $i$ 位士兵的军衔。如果有多种方案，输出任意一种均可。 如果无解，只需输出一个数 $-1$。

由 ChatGPT 5 翻译