Berland Army

题意翻译

**题意:** $n$ 个点, $m$ 条有向边, 所有点的点权在$1~k$ 中且一部分点权已知, 希望确定一种方案满足: 1.对于所有由$x$ 指向$y$ 的边, $x$ 的点权大于$y$ 2.对于$i=1,2,...,k$ , 至少有一个点的点权为$i$ **输入:** 第一行三个整数$n,m,k(1<=n,k<=2*10^5,0<=m<=2*10^5)$ 第二行$n$ 个整数$r_i$ , 若$1<=r_i<=k$ 表示第$i$ 个点的权值为$r_i$ , 若$r_i=0$ 表示该点的权值未知 接下来$m$ 行, 每行两个整数$x_i,y_i(1<=x_i,y_i<=n,x_i≠y_i)$ , 表示由$x_i$ 到$y_i$ 的有向边 **输出:** 无解输出$-1$ , 否则一行$n$ 个数,表示第$i$ 个点的点权 感谢@凌幽 提供的翻译

题目描述

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.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ and $ k $ ( $ 1<=n<=2·10^{5} $ , $ 0<=m<=2·10^{5} $ , $ 1<=k<=2·10^{5} $ ) — 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 $ .

输出格式

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.

输入输出样例

输入样例 #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

题意翻译

**题意:** $n$ 个点, $m$ 条有向边, 所有点的点权在$1~k$ 中且一部分点权已知, 希望确定一种方案满足: 1.对于所有由$x$ 指向$y$ 的边, $x$ 的点权大于$y$ 2.对于$i=1,2,...,k$ , 至少有一个点的点权为$i$ **输入:** 第一行三个整数$n,m,k(1<=n,k<=2*10^5,0<=m<=2*10^5)$ 第二行$n$ 个整数$r_i$ , 若$1<=r_i<=k$ 表示第$i$ 个点的权值为$r_i$ , 若$r_i=0$ 表示该点的权值未知 接下来$m$ 行, 每行两个整数$x_i,y_i(1<=x_i,y_i<=n,x_i≠y_i)$ , 表示由$x_i$ 到$y_i$ 的有向边 **输出:** 无解输出$-1$ , 否则一行$n$ 个数,表示第$i$ 个点的点权 感谢@凌幽 提供的翻译