CF986A.Fair

Some company is going to hold a fair in Byteland. There are $n$ towns in Byteland and $m$ two-way roads between towns. Of course, you can reach any town from any other town using roads.

There are $k$ types of goods produced in Byteland and every town produces only one type. To hold a fair you have to bring at least $s$ different types of goods. It costs $d(u,v)$ coins to bring goods from town $u$ to town $v$ where $d(u,v)$ is the length of the shortest path from $u$ to $v$. Length of a path is the number of roads in this path.

The organizers will cover all travel expenses but they can choose the towns to bring goods from. Now they want to calculate minimum expenses to hold a fair in each of $n$ towns.

某公司将在比特兰（Byteland）举办一场展销会。比特兰共有 $n$ 座城镇和 $m$ 条连接城镇的双向道路。显然，任意两座城镇之间均可通过道路相互到达。

比特兰共生产 $k$ 种商品，且每座城镇仅生产其中一种。要举办一场展销会，必须至少汇集 $s$ 种不同类别的商品。将商品从城镇 $u$ 运送至城镇 $v$ 的花费为 $d(u,v)$ 枚金币，其中 $d(u,v)$ 表示 $u$ 到 $v$ 的最短路径长度（即该路径所含道路的数量）。

主办方将承担全部运输费用，但他们可自主选择从哪些城镇调运商品。现在，他们希望计算在每一座城镇举办展销会所需的最小总费用。

There are $4$ integers $n$, $m$, $k$, $s$ in the first line of input ($1 \le n \le 10^{5}$, $0 \le m \le 10^{5}$, $1 \le s \le k \le min(n, 100)$) — the number of towns, the number of roads, the number of different types of goods, the number of different types of goods necessary to hold a fair.

In the next line there are $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_{i} \le k$), where $a_i$ is the type of goods produced in the $i$-th town. It is guaranteed that all integers between $1$ and $k$ occur at least once among integers $a_{i}$.

In the next $m$ lines roads are described. Each road is described by two integers $u$ $v$ ($1 \le u, v \le n$, $u \ne v$) — the towns connected by this road. It is guaranteed that there is no more than one road between every two towns. It is guaranteed that you can go from any town to any other town via roads.

输入的第一行包含 $4$ 个整数 $n$、$m$、$k$、$s$（$1 \le n \le 10^{5}$，$0 \le m \le 10^{5}$，$1 \le s \le k \le \min(n, 100)$），分别表示城镇数量、道路数量、商品种类总数、举办集市所需的不同商品种类数。

接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_{i} \le k$），其中 $a_i$ 表示第 $i$ 个城镇所生产商品的种类。保证在所有 $a_i$ 中，$1$ 到 $k$ 之间的每个整数至少出现一次。

接下来 $m$ 行描述道路。每条道路由两个整数 $u$、$v$（$1 \le u, v \le n$，$u \ne v$）描述，表示连接城镇 $u$ 和 $v$ 的一条道路。保证任意两个城镇之间至多只有一条道路。保证通过道路可以从任意一个城镇到达任意其他城镇。

Print $n$ numbers, the $i$-th of them is the minimum number of coins you need to spend on travel expenses to hold a fair in town $i$. Separate numbers with spaces.

输出 $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$.

我们来看第一个样例。

在城镇 $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$。