//我们直接将所有生产i型商品的城市一次性全加入队列，然后bfs
//前言 对于 n个城市 每一个城市只会生产一种商品可能是相同的 一共有k种 需要找到s种商品 其中s<=k 来举办一共fair
//解题思路 以把生产同一种产品的城市看成一个集合 对于每一个要举办fair的城市而言 只需要把
//每种产品集合中 到达举办城市的最短路加起来就是最小值了 因此只需要以举办城市为源进行 二维多源bfs即可

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+5;
int n,m,k,s;//n代表一共有n个城市,m代表有m条双向连通的边 一共有k种商品 s代表在某城举办一次fair所需要集齐的最少的商品的种类数 
int good[MAX],mov[MAX][105];//
vector<int> E[MAX];// 
void bfs(int x)
{
    queue<int> Q;
    int i,u,v;
    Q.push(x+n);//除了开始第一轮的搜索是使用了一个边界外的点来给所有 生产x产品的城市赋初值以外 所有后边的搜索都是对每一个城市以及他所连接到的城市进行搜索并赋值最短路 
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        for(i=0;i<E[u].size();i++){
            v=E[u][i];//当前生产商品为u的城市是E[u][i]; 
            if(mov[v][x]==0){//对于每个城市而言谁先从x起点出发到达v 那个先到那个就是最小值0代表还没有其他点搜到过 
                mov[v][x]=mov[u][x]+1;//对距离+1即可 
                Q.push(v);//该距离改变后把新的点放入队列以便更新和v相连通的点 
            }
        }
    }
}
int main()
{
    int i,j;
    int u,v,cnt;
    scanf("%d%d%d%d",&n,&m,&k,&s);
    for(i=1;i<=n;i++){
        scanf("%d",&good[i]);
        E[good[i]+n].push_back(i);//把生产同一种产品的城市 用一个二维线性容器的方式 每一个物品代表一种类 里面存了所有该生产该商品的城市 
    }
    for(i=0;i<m;i++){
        scanf("%d%d",&u,&v);//路是双向的 
        E[u].push_back(v);//以u为起点出发可以直接连通到的城市存入一个容器种 
        E[v].push_back(u);//同理路是双向的 也要对v进行同样的操作 
    }
    for(i=1;i<=k;i++) bfs(i);
    for(i=1;i<=n;i++){//一共有n个输出 第i个输出代表的是在第i个城镇举办一次fair所需要花费的最少的硬币数 
        cnt=0;
        sort(mov[i]+1,mov[i]+k+1);//对k种物品到城市i的距离也就是花费进行升序排序 
        for(j=1;j<=s;j++)//只需要选取s种即可 
            cnt+=mov[i][j]-1;//由于初始话时为了减少时间以及空间复杂度 将初始距离置成1 来实现对最短路的标记 需要对每一个最短路再减去一个一才是真实值 
        printf("%d ",cnt);
    }
    return 0;
}