http://codeforces.com/problemset/problem/883/B
给有向图，某些点点权已知，确定其他未知点权，使得：
- 所有点权在 \([1,k]\) 之间
- 对于边 \(x\rightarrow y\)，\(x\) 的点权大于 \(y\) 的
- 对于所有的 \(i\in [1,k]\)，都有至少一个点点权为 \(i\)
考虑先正反两边找到每一个点的最大、最小点权，记为 \([l_u,r_u]\)。然后对于每个 \(i\) 确定哪些点的点权为 \(i\)，使得在不违反条件 2 的情况下尽量去满足条件 3
此时点权 \([1,i-1]\) 必然已经被分配完，记 \(S\) 为所有 \(l_u\le i\) 的 \(u\) 的集合
那么对于所有的 \(r_u=i\) 的 \(u\)，都要分配点权为 \(i\)。因为如果分配成 \(j<i\) 的话，由于存在已经被分配成 \(j\) 的点，可能会产生冲突违反条件 2。而显然把他们分配为 \(i\) 也更符合条件 3
若不存在 \(r_u=i\) 的点，则需要取一个 \(r_u>i\) 的点分配为 \(i\)。此时对于条件 3，显然取 \(r_u\) 最小的最优
如果此时仍然没有 \(r_u>i\) 的点，则为无解
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<utility>
#include<set>
#define reg register
#define EN puts("")
#define INT_INF ((int)0x3f3f3f3f)
#define LL_INF ((long long)0x3f3f3f3f3f3f3f3f)
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<‘0‘||c>‘9‘){if(c==‘-‘) y=0;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){x=x*10+(c^48);c=getchar();}
return y?x:-x;
}
#define N 200006
#define M 200006
struct Graph{
int fir[N],nex[M],to[M],tot;
inline void add(int u,int v){
to[++tot]=v;
nex[tot]=fir[u];fir[u]=tot;
}
};
Graph G,T;
int n,m,k;
int val[N];
int in[N],out[N];
int min[N],max[N],id[N];
int left,right,que[N];
inline int topo1(){
left=0;right=-1;
for(reg int i=1;i<=n;i++)if(!out[i]) min[i]=val[i]?val[i]:1,que[++right]=i;
reg int u,i,v;while(left<=right){
u=que[left++];
for(i=T.fir[u];i;i=T.nex[i]){
v=T.to[i];
min[v]=std::max(min[v],min[u]+1);
if(!--out[v]){
if(val[v]&&val[v]<min[v]) return 1;
min[v]=std::max(min[v],val[v]);
que[++right]=v;
}
}
}
for(reg int i=1;i<=n;i++)if(out[i]) return 1;
return 0;
}
inline int topo2(){
left=0;right=-1;
for(reg int i=1;i<=n;i++){
if(!in[i]) max[i]=val[i]?val[i]:k,que[++right]=i;
else max[i]=k;
}
reg int u,i,v;while(left<=right){
u=que[left++];
for(i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
max[v]=std::min(max[v],max[u]-1);
if(!--in[v]){
if(val[v]&&val[v]>max[v]) return 1;
if(val[v]) max[v]=std::min(max[v],val[v]);
que[++right]=v;
}
}
}
for(reg int i=1;i<=n;i++)if(in[i]) return 1;
return 0;
}
int ans[N];
std::set<std::pair<int,int> >set;
int main(){
n=read();m=read();k=read();
for(reg int i=1;i<=n;i++) val[i]=read();
for(reg int u,v,i=1;i<=m;i++){
u=read();v=read();
in[v]++;out[u]++;
G.add(u,v);T.add(v,u);
}
if(topo1()||topo2()) return puts("-1"),0;
for(reg int i=1;i<=n;i++)if(min[i]>max[i]) return puts("-1"),0;
// for(reg int i=1;i<=n;i++) printf("%d : [%d %d]\n",i,min[i],max[i]);
for(reg int i=1;i<=n;i++) id[i]=i;
std::sort(id+1,id+1+n,[](reg int a,reg int b){return min[a]==min[b]?max[a]<max[b]:min[a]<min[b];});
for(reg int now=1,i=1;i<=k;i++){
while(now<=n&&min[id[now]]<=i) set.insert(std::make_pair(max[id[now]],id[now])),now++;
int have=0;
while(!set.empty()){
int id=(*set.begin()).second;
if(have&&max[id]>i) break;
ans[id]=i;have=1;
set.erase(set.begin());
}
if(!have) return puts("-1"),0;
}
for(reg int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}