English · Original
Chinese · Translation
Formal · Original
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_.
It 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.
Help the ministry to assign ranks to the rest of the army so that:
* 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_);
* for each rank from 1 to _k_ there is at least one military man with this rank.
## Input
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.
The 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.
The 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_.
## Output
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.
If there is no solution, print the only number _\-1_.
[samples]
贝兰军队中有 #cf_span[n] 名军人。目前，部分军人已向其他军人下达过命令。给定 #cf_span[m] 对 (#cf_span[xi], #cf_span[yi])，表示军人 #cf_span[xi] 向军人 #cf_span[yi] 发出了第 #cf_span[i] 条命令。
现在是改革的时候了！贝兰国防部计划在军队中引入军衔制度。每位军人应被分配一个介于 #cf_span[1] 和 #cf_span[k] 之间（含端点）的整数作为军衔。部分军人已分配了军衔，其余的则需尽快分配。
请帮助国防部为剩余的军人分配军衔，使得：
第一行包含三个整数 #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] 的命令。
请输出 #cf_span[n] 个整数，其中第 #cf_span[i] 个数表示第 #cf_span[i] 名军人的军衔。如果有多种解，请输出任意一种。
如果无解，请仅输出 _-1_。
## Input
第一行包含三个整数 #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] 的命令。
## Output
请输出 #cf_span[n] 个整数，其中第 #cf_span[i] 个数表示第 #cf_span[i] 名军人的军衔。如果有多种解，请输出任意一种。如果无解，请仅输出 _-1_。
[samples]
**Definitions**
Let $ n, m, k \in \mathbb{Z}^+ $ denote the number of military men, orders, and possible ranks, respectively.
Let $ 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.
Let $ 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 $.
**Constraints**
1. For each edge $ (x, y) \in E $, it must hold that $ r_x > r_y $.
2. For each $ i \in [n] $, if $ r_i > 0 $, then $ r_i \in [1, k] $.
3. For each $ i \in [n] $ with $ r_i = 0 $, assign $ r_i \in [1, k] $.
**Objective**
Assign 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 $.
If no such assignment exists, output $-1$.
Otherwise, output the full rank vector $ (r_1, r_2, \dots, r_n) $.
API Response (JSON)
{
"problem": {
"name": "B. Berland Army",
"description": {
"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 ord",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF883B"
},
"statements": [
{
"statement_type": "Markdown",
"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 ord...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"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] 和...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**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 pa...",
"is_translate": false,
"language": "Formal"
}
]
}