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$个城镇举办商品交易会所需花在运输上的最小费用。数与数之间用空格分开。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5

输出样例 #1

2 2 2 2 3 

输入样例 #2

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

输出样例 #2

1 1 1 2 2 1 1 

说明

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