某公司将在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$$$。