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