#include<bits/stdc++.h>
using namespace std;
const int o=5e5+10;
int n,m,K,h[o],cnt,c[o];bool vis[o];double w[o];set<int> ban[o];mt19937 rnd(time(0));
struct Edge{int v,p;}e[o*2];
inline void ad(int U,int V){e[++cnt].v=V;e[cnt].p=h[U];h[U]=cnt;}
void dfs(int nw){
	if(vis[nw]) return;
	vis[nw]=1;
	for(int i=h[nw];i;i=e[i].p) if(c[e[i].v]==(c[nw]+1)%K||c[nw]==(c[e[i].v]+1)%K) dfs(e[i].v);
}
inline bool chk(){
	for(int i=1;i<=n;++i) if(!vis[i]) return false;
	return true;
}
struct info{
	int u,c;double w;
	inline bool operator<(const info&b)const{return w<b.w;}
};
priority_queue<info> q;
int main(){
	scanf("%d%d%d",&n,&m,&K);
	for(int i=1;i<=n;++i) scanf("%d",&c[i]),--c[i];
	for(int u,v;m--;) scanf("%d%d",&u,&v),ad(u,v),ad(v,u);
	dfs(1);
	for(;!chk();){
		for(int i=1;i<=n;++i) vis[i]=0,set<int>().swap(ban[i]),w[i]=rnd()%10000*0.07/10000+0.93;
		q.push((info){(int)(rnd()%n+1),0,0.0});
		for(int u,col,d;!q.empty();){
			u=q.top().u;col=q.top().c;q.pop();
			if(vis[u]) continue;
			d=((rnd()&1)?K-1:1);
			if(ban[u].find((col+d)%K)==ban[u].end()){
				c[u]=(col+d)%K;vis[u]=1;
				for(int i=h[u];i;i=e[i].p) if(!vis[e[i].v])
					ban[e[i].v].insert(c[u]),q.push((info){e[i].v,c[u],w[e[i].v]*(double)ban[e[i].v].size()});
			}
			else if(ban[u].find((col+K-d)%K)==ban[u].end()){
				c[u]=(col+K-d)%K;vis[u]=1;
				for(int i=h[u];i;i=e[i].p) if(!vis[e[i].v])
					ban[e[i].v].insert(c[u]),q.push((info){e[i].v,c[u],w[e[i].v]*(double)ban[e[i].v].size()});
			}
		}
	}
	for(int i=1;i<=n;++i) printf("%d ",c[i]+1);
	return 0;
}