[R30E]彩色小球 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有 $n$ 个小球，它们从 $1$ 到 $n$ 编号。每个小球 $i$ 都有一个颜色 $c_i$，且第 $i$ 个小球上写有数字 $i$。

现在需要将这 $n$ 个小球从左到右排成一排，这个排列需要满足以下两个条件：

• 所有相同颜色的小球必须形成一个连续的块。
• 给定 $m$ 个限制条件，每个限制形如 $(u_i, v_i)$，表示编号为 $u_i$ 的小球必须出现在编号为 $v_i$ 的小球的左边。

你的任务是找到一个满足所有条件的排列，并使得该排列（由小球编号组成）的字典序最小。如果没有满足条件的排列，输出 -1。

字典序：对于两个长度为 $n$ 的序列 $A = (a_1, a_2, \ldots, a_n)$ 和 $B = (b_1, b_2, \ldots, b_n)$，如果存在一个位置 $k$ 使得对于所有 $j < k$ 都有 $a_j = b_j$，并且 $a_k < b_k$，那么我们称序列 $A$ 的字典序小于序列 $B$。

格式

输入格式

第一行包含两个整数 $n, m$，分别表示小球的数量和限制条件的数量。

第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$，表示编号为 $i$ 的小球的颜色是 $c_i$。

接下来 $m$ 行，每行包含两个整数 $u_i, v_i$，表示一个限制条件。

输出格式

输出一行 $n$ 个整数，代表字典序最小的小球编号序列。整数之间用空格隔开。

如果不存在这样的排列，则输出 -1。

样例

样例输入 #1

4 1
1 2 1 2
3 1

样例输出 #1

2 4 3 1

样例输入 #2

4 1
1 2 1 2
1 4

样例输出 #2

1 3 2 4

数据规模

对于 $10\%$ 的数据，$1 \leq n ,m \leq 10$。

对于 $40\%$ 的数据，$1 \le n, m \le 2000$。

对于 $100\%$ 的数据，$1 \le n, m \le 2 \times 10^5$，$1 \le c_i \le n$，$1 \le u_i, v_i \le n$，且 $u_i \not = v_i$。