← 返回题目列表

Codeforces · 986/A

A. 公平

中文机器翻译题面 查看原题

某公司将在Byteland举办展会。 Byteland 有 $$$n$$$ 个城镇,城镇之间有 $$$m$$$ 双向道路。当然,您可以通过道路从任何其他城镇到达任何城镇。

Byteland 生产的商品有 $$$k$$$ 种,每个城镇只生产一种。要举办博览会,您必须至少携带 $$$s$$$ 不同类型的商品。将货物从镇 $$$u$$$ 运到镇 $$$v$$$ 需要花费 $$$d(u,v)$$$ 硬币,其中 $$$d(u,v)$$$ 是从 $$$u$$$ 到 $$$v$$$ 的最短路径的长度。路径的长度是指该路径中道路的数量。

组织者将承担所有旅行费用,但他们可以选择带货的城镇。现在他们想要计算在每个 $$$n$$$ 城镇举办博览会的最低费用。

输入

输入第一行有 $$$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$$$ 镇生产的商品类型。保证$$$1$$$和$$$k$$$之间的所有整数在整数$$$a_{i}$$$中至少出现一次。

在接下来的 $$$m$$$ 行中描述了道路。每条道路由两个整数 $$$u$$$ $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) 描述 - 由这条道路连接的城镇。保证每两个城镇之间不超过一条道路。保证您可以通过公路从任何城镇前往任何其他城镇。

输出

打印 $$$n$$$ 数字,其中第 $$$i$$$ 是您在镇上 $$$i$$$ 举办集市所需的旅费的最低硬币数量。用空格分隔数字。

示例

输入 #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

注意

让我们看一下第一个示例。

要在镇上举办集市$$$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$$$。