CF986A Fair

一些公司将在 Byteland 举办商品交易会（or 博览会？）。在 Byteland 有 $n$ 个城市，城市间有 $m$ 条双向道路。当然，城镇之间两两连通。 Byteland 生产的货物有 $k$ 种类型，每个城镇只生产一种。 为了举办商品交易会，你必须至少带来 $s$ 种不同类型的商品。将货物从 $u$ 镇带到城镇 $v$ 将花费 $d(u,v)$ 的费用，其中 $d(u,v)$ 是从 $u$ 到 $v$ 的最短路径的长度。 路径的长度是这个路径中的道路的数量。 组织者将支付所有的运输费用，但他们可以选择从哪些城镇带来货物。现在他们想计算每个城镇举办商品交易会的最小费用。

第一行 $4$ 个整数 $n,m,k,s(1\le n\le 10^5 $,$1\le m\le 10^5 $,$1\le s\le k\le min(n,100) )$——分别表示 城镇数，道路数，生产的货物数，举办商品交易会所需的货物数。 接下来一行 $n$ 个整数 $a_1,a_2,...,a_n(1\le a_i \le k)$ , $a_i$ 是第 $i$ 个城镇生产的商品种类.保证 $1$ 和$k$之间的所有整数在整数 $a_i$ 中至少出现一次。 接下来$m$行表示道路。每行两个整数 $u,v$ $(1 \le u,v \le n, u\ne v)$ 表示 $u,v$ 之间有一条双向道路。保证每两个城镇之间只有一条路。并且城镇之间两两连通。

输出 $n$ 个数。第 $i$ 个数表示在第 $i$ 个城镇举办商品交易会所需花在运输上的最小费用。数与数之间用空格分开。

Let's look at the first sample. To hold a fair in town $ 1 $ you can bring goods from towns $ 1 $ ( $ 0 $ coins), $ 2 $ ( $ 1 $ coin) and $ 4 $ ( $ 1 $ coin). Total numbers of coins is $ 2 $ . Town $ 2 $ : Goods from towns $ 2 $ ( $ 0 $ ), $ 1 $ ( $ 1 $ ), $ 3 $ ( $ 1 $ ). Sum equals $ 2 $ . Town $ 3 $ : Goods from towns $ 3 $ ( $ 0 $ ), $ 2 $ ( $ 1 $ ), $ 4 $ ( $ 1 $ ). Sum equals $ 2 $ . Town $ 4 $ : Goods from towns $ 4 $ ( $ 0 $ ), $ 1 $ ( $ 1 $ ), $ 5 $ ( $ 1 $ ). Sum equals $ 2 $ . Town $ 5 $ : Goods from towns $ 5 $ ( $ 0 $ ), $ 4 $ ( $ 1 $ ), $ 3 $ ( $ 2 $ ). Sum equals $ 3 $ .