Problem1115--买球

1115: 买球

[Creator : ]
Time Limit : 5.000 sec  Memory Limit : 128 MB

Description

CSU镇上有n个商店,n个商店有m条双向小路相连,在这n个商店里共有k个不同小球,每个商店只有一种小球。现小p从某个商店出发,买够k个不同小球中的s个小球。小p有分身术,在出发商店时,会变k-1个分身,让这些分身各自买一种球,自己在初始商店买一个球。计算从每个商店出发买够k个球分身需要通过的最小条路数量和。

Input

本题目包含多组数据,对于每一组第一行输入包含四个数字n ,m, k,s (1<=n<=m<=10^5 , 1<=s<=k<=min(n,100))分别代表商店数,小路数,小球数,需要的小球数。接下来一行n个数 a1,a2...ak (1<=ai<=k),ai代表第i个商店的小球编号。接下来m行为小路(u,v),u≠v,代表商店uv之间有小路连接。

Output

输出n个数字,第i个数字代表从商店i出发买够s个小球所需通过的最小小路数量和。如果无法买够s个小球输出-1

Sample Input Copy

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 Copy

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