403004 - 商品交易会

有 n 个城市，m 条双向道路，整张图连通。每个城市生产一种商品（共 k 种）。现在每个城市要举办一场商品交易会，需要至少 s 种不同商品（可以包括自己生产的）。 将商品从一个城市运到另一个城市的运费等于两城市之间最短路径的道路条数；每种商品选择一个产出该商品的城市供货，总运费为选出的 s 个城市到当前城市的距离之和。求每个城市对应的最小总运费。

第一行 4 个整数 n, m, k, s（1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5, 1 ≤ s ≤ k ≤ min(n, 100)）分别表示城市数，道路数，生产的商品数，举办商品交易会所需的商品数。 接下来一行 n 个整数 a1, a2, ..., an（1 ≤ ai ≤ k）, ai 是第 i 个城镇生产的商品种类.保证 1 到 k 之间的所有整数在整数 ai 中至少出现一次。 接下来 m 行，每行两个整数 u, v（1 ≤ u, v ≤ n, u ≠ v）代表 u、v 之间的一条双向道路。图中无重边，整张图连通。

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

第一组样例： 在 1 号城市办交易会：取自 1 号 (花费 0)、2 号 (花费 1)、4 号 (花费 1)，总花费 2。 2 号城市：取自 2 号 (0)、1 号 (1)、3 号 (1)，总和 2。 3 号城市：取自 3 号 (0)、2 号 (1)、4 号 (1)，总和 2。 4 号城市：取自 4 号 (0)、1 号 (1)、5 号 (1)，总和 2。 5 号城市：取自 5 号 (0)、4 号 (1)、3 号 (2)，总和 3。