Problem1211--小镇购物

1211: 小镇购物

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 390  Solved: 180
[Submit] [Status] [Web Board] [Creator:]

Description

CSU镇上有n个商店,n个商店有m条双向小路相连,在这n个商店里共有k种不同商品,每个商店只有一种商品,每条路的权重都为1。现问你从每个商店出发,买够k种商品中的s种商品所需的最小代价,每个商店可以同时派出多个人买不同商品,买够即可。

Input

输入包含多组测试用例。
对于每一组输入包含四个数字n ,m, k,s (1<=n<=m<=1e5 , 1<=s<=k<=min(n,100))
分别代表商店数,小路数,商品种数,需要的商品数。
接下来n个数 a1,a2...an (1<=ai<=k),ai代表第i个商店的商品编号。
接下来m行小路(u,v),u≠v,代表商店u和v之间有小路连接。

Output

输出n个数字,第i个数字代表从商店i出发买够s种商品所需的最小代价。

Sample Input

5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5
7 6 3 2
1 2 3 3 2 2 1
1 2
2 3
3 4
2 5
5 6
6 7

Sample Output

2 2 2 2 3 
1 1 1 2 2 1 1