← 返回题目列表

Codeforces · 883/B

B. 贝尔兰德陆军

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

Berland军队中有n名军人。他们中的一些人现在已经向其他军人发出了命令。给定 m 对 (xi, yi),表示军人 xi 将第 i 个命令下达给另一名军人 yi。

是时候改革了!贝尔兰国防部计划在贝尔兰军队中引入军衔。每个军人都应该被分配一个军衔——1 到 k 之间的整数(含 1 和 k)。他们中的一些人已经获得了军衔,但其余的人应该很快就会获得军衔。

帮助国防部为军队其他人员分配军衔,以便:

- 对于 m 个命令中的每一个,发出命令的人(军人 xi)的军衔确实严格高于接受命令的人(军人 yi)的军衔;
- 对于从 1 到 k 的每个军衔,至少有一名军人具有该军衔。

输入

第一行包含三个整数 n、m 和 k (1 ≤ n ≤ 2·105, 0 ≤ m ≤ 2·105, 1 ≤ k ≤ 2·105) — Berland 军队的军人数量、军衔数量和军衔数量。

第二行包含 n 个整数 r1, r2, ..., rn,其中 ri > 0(在这种情况下 1 ≤ ri ≤ k)意味着第 i 个军人已经被分配了军衔 ri; ri = 0 表示第 i 个军人还没有军衔。

以下 m 行每行包含一个订单。每个阶数用一行包含两个整数 xi, yi (1 ≤ xi, yi ≤ n, xi ≠ yi) 来描述。这行表示第 i 个命令是由军人喜给军人易下达的。对于每对 (x, y) 军人,可能有从 x 到 y 的多个命令。

输出

打印n个整数,其中第i个数字是第i个军人的军衔。如果有很多解决方案,请打印其中任何一个。

如果无解,则打印唯一的数字-1。

示例

输入 #1

5 3 3
0 3 0 0 2
2 4
3 4
3 5

输出 #1

1 3 3 2 2

输入 #2

7 6 5
0 4 5 4 1 0 0
6 1
3 6
3 1
7 5
7 1
7 4

输出 #2

2 4 5 4 1 3 5

输入 #3

2 2 2
2 1
1 2
2 1

输出 #3

-1