{"raw_statement":[{"iden":"statement","content":"There are _n_ military men in the Berland army. Some of them have given orders to other military men by now. Given _m_ pairs (_x__i_, _y__i_), meaning that the military man _x__i_ gave the _i_\\-th order to another military man _y__i_.\n\nIt is time for reform! The Berland Ministry of Defence plans to introduce ranks in the Berland army. Each military man should be assigned a rank — integer number between 1 and _k_, inclusive. Some of them have been already assigned a rank, but the rest of them should get a rank soon.\n\nHelp the ministry to assign ranks to the rest of the army so that:\n\n*   for each of _m_ orders it is true that the rank of a person giving the order (military man _x__i_) is strictly greater than the rank of a person receiving the order (military man _y__i_);\n*   for each rank from 1 to _k_ there is at least one military man with this rank."},{"iden":"input","content":"The first line contains three integers _n_, _m_ and _k_ (1 ≤ _n_ ≤ 2·105, 0 ≤ _m_ ≤ 2·105, 1 ≤ _k_ ≤ 2·105) — number of military men in the Berland army, number of orders and number of ranks.\n\nThe second line contains _n_ integers _r_1, _r_2, ..., _r__n_, where _r__i_ > 0 (in this case 1 ≤ _r__i_ ≤ _k_) means that the _i_\\-th military man has been already assigned the rank _r__i_; _r__i_ = 0 means the _i_\\-th military man doesn't have a rank yet.\n\nThe following _m_ lines contain orders one per line. Each order is described with a line containing two integers _x__i_, _y__i_ (1 ≤ _x__i_, _y__i_ ≤ _n_, _x__i_ ≠ _y__i_). This line means that the _i_\\-th order was given by the military man _x__i_ to the military man _y__i_. For each pair (_x_, _y_) of military men there could be several orders from _x_ to _y_."},{"iden":"output","content":"Print _n_ integers, where the _i_\\-th number is the rank of the _i_\\-th military man. If there are many solutions, print any of them.\n\nIf there is no solution, print the only number _\\-1_."},{"iden":"examples","content":"Input\n\n5 3 3\n0 3 0 0 2\n2 4\n3 4\n3 5\n\nOutput\n\n1 3 3 2 2 \n\nInput\n\n7 6 5\n0 4 5 4 1 0 0\n6 1\n3 6\n3 1\n7 5\n7 1\n7 4\n\nOutput\n\n2 4 5 4 1 3 5 \n\nInput\n\n2 2 2\n2 1\n1 2\n2 1\n\nOutput\n\n\\-1"}],"translated_statement":[{"iden":"statement","content":"贝兰军队中有 #cf_span[n] 名军人。目前，部分军人已向其他军人下达过命令。给定 #cf_span[m] 对 (#cf_span[xi], #cf_span[yi])，表示军人 #cf_span[xi] 向军人 #cf_span[yi] 发出了第 #cf_span[i] 条命令。\n\n现在是改革的时候了！贝兰国防部计划在军队中引入军衔制度。每位军人应被分配一个介于 #cf_span[1] 和 #cf_span[k] 之间（含端点）的整数作为军衔。部分军人已分配了军衔，其余的则需尽快分配。\n\n请帮助国防部为剩余的军人分配军衔，使得：\n\n第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 2·105], #cf_span[0 ≤ m ≤ 2·105], #cf_span[1 ≤ k ≤ 2·105]) —— 分别表示贝兰军队中的军人数量、命令数量和军衔等级数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[r1, r2, ..., rn]，其中 #cf_span[ri > 0]（此时 #cf_span[1 ≤ ri ≤ k]）表示第 #cf_span[i] 名军人已被分配军衔 #cf_span[ri]；#cf_span[ri = 0] 表示第 #cf_span[i] 名军人尚未分配军衔。\n\n接下来的 #cf_span[m] 行每行包含一条命令。每条命令由两个整数 #cf_span[xi], #cf_span[yi] 描述（#cf_span[1 ≤ xi, yi ≤ n], #cf_span[xi ≠ yi]），表示第 #cf_span[i] 条命令由军人 #cf_span[xi] 下达给军人 #cf_span[yi]。对于每对军人 (#cf_span[x], #cf_span[y])，可能存在多条从 #cf_span[x] 到 #cf_span[y] 的命令。\n\n请输出 #cf_span[n] 个整数，其中第 #cf_span[i] 个数表示第 #cf_span[i] 名军人的军衔。如果有多种解，请输出任意一种。\n\n如果无解，请仅输出 _-1_。\n\n"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 2·105], #cf_span[0 ≤ m ≤ 2·105], #cf_span[1 ≤ k ≤ 2·105]) —— 分别表示贝兰军队中的军人数量、命令数量和军衔等级数量。第二行包含 #cf_span[n] 个整数 #cf_span[r1, r2, ..., rn]，其中 #cf_span[ri > 0]（此时 #cf_span[1 ≤ ri ≤ k]）表示第 #cf_span[i] 名军人已被分配军衔 #cf_span[ri]；#cf_span[ri = 0] 表示第 #cf_span[i] 名军人尚未分配军衔。接下来的 #cf_span[m] 行每行包含一条命令。每条命令由两个整数 #cf_span[xi], #cf_span[yi] 描述（#cf_span[1 ≤ xi, yi ≤ n], #cf_span[xi ≠ yi]），表示第 #cf_span[i] 条命令由军人 #cf_span[xi] 下达给军人 #cf_span[yi]。对于每对军人 (#cf_span[x], #cf_span[y])，可能存在多条从 #cf_span[x] 到 #cf_span[y] 的命令。"},{"iden":"output","content":"请输出 #cf_span[n] 个整数，其中第 #cf_span[i] 个数表示第 #cf_span[i] 名军人的军衔。如果有多种解，请输出任意一种。如果无解，请仅输出 _-1_。"},{"iden":"examples","content":"输入\n5 3 3\n0 3 0 0 2\n2 4\n3 4\n3 5\n输出\n1 3 3 2 2\n\n输入\n7 6 5\n0 4 5 4 1 0 0\n6 1\n3 6\n3 1\n7 5\n7 1\n7 4\n输出\n2 4 5 4 1 3 5\n\n输入\n2 2 2\n2 1\n1 2\n2 1\n输出\n-1"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, k \\in \\mathbb{Z}^+ $ denote the number of military men, orders, and possible ranks, respectively.  \nLet $ R = (r_1, r_2, \\dots, r_n) \\in (\\{0\\} \\cup [1, k])^n $ be the partial rank assignment, where $ r_i = 0 $ means unassigned.  \nLet $ G = (V, E) $ be a directed multigraph with $ V = \\{1, 2, \\dots, n\\} $ and $ E = \\{(x_i, y_i) \\mid i \\in [m]\\} $, representing orders: an edge $ x \\to y $ means $ x $ gave an order to $ y $.\n\n**Constraints**  \n1. For each edge $ (x, y) \\in E $, it must hold that $ r_x > r_y $.  \n2. For each $ i \\in [n] $, if $ r_i > 0 $, then $ r_i \\in [1, k] $.  \n3. For each $ i \\in [n] $ with $ r_i = 0 $, assign $ r_i \\in [1, k] $.\n\n**Objective**  \nAssign values to $ r_i $ for all $ i $ with $ r_i = 0 $, such that for every directed edge $ (x, y) \\in E $, $ r_x > r_y $.  \nIf no such assignment exists, output $-1$.  \nOtherwise, output the full rank vector $ (r_1, r_2, \\dots, r_n) $.","simple_statement":null,"has_page_source":false}