공정한 박람회

어떤 회사가 Byteland에서 박람회를 개최하려 한다. Byteland에는 n개의 도시와 도시 사이를 잇는 m개의 양방향 도로가 있다. 물론 도로를 이용하면 어느 도시에서든 다른 모든 도시에 도달할 수 있다.

Byteland에서는 k가지 종류의 상품이 생산되며, 각 도시는 단 한 종류의 상품만 생산한다. 박람회를 개최하려면 적어도 s가지 서로 다른 종류의 상품을 가져와야 한다. 도시 u에서 도시 v로 상품을 가져오는 데에는 d(u,v)개의 동전이 들며, 여기서 d(u,v)는 u에서 v까지의 최단 경로의 길이이다. 경로의 길이는 이 경로에 포함된 도로의 수이다.

주최 측은 모든 운송 비용을 부담하지만, 상품을 가져올 도시들은 선택할 수 있다. 이제 주최 측은 n개 도시 각각에서 박람회를 개최하는 데 필요한 최소 비용을 계산하려 한다.

입력의 첫 줄에 도시의 수, 도로의 수, 서로 다른 상품 종류의 수, 박람회를 개최하는 데 필요한 서로 다른 상품 종류의 수를 나타내는 4개의 정수 n, m, k, s가 주어진다 (1 ≤ n ≤ $10^{5}$, 0 ≤ m ≤ $10^{5}$, 1 ≤ s ≤ k ≤ min(n, 100)).

다음 줄에는 n개의 정수 $a_1$, $a_2$, …, $a_n$ (1 ≤ $a_{i}$ ≤ k)가 주어지며, 여기서 $a_i$는 i-th번째 도시에서 생산되는 상품의 종류이다. 1부터 k까지의 모든 정수가 정수들 $a_{i}$ 사이에 적어도 한 번씩 등장함이 보장된다.

다음 m개의 줄에는 도로가 설명된다. 각 도로는 이 도로로 연결된 도시들을 나타내는 두 정수 u v (1 ≤ u, v ≤ n, u ≠ v)로 설명된다. 임의의 두 도시 사이에는 도로가 최대 하나만 있음이 보장된다. 도로를 통해 어느 도시에서든 다른 모든 도시로 갈 수 있음이 보장된다.

n개의 수를 출력한다. 그중 i-th번째 수는 도시 i에서 박람회를 개최하기 위해 운송 비용으로 지출해야 하는 최소 동전 수이다. 수들은 공백으로 구분한다.

첫 번째 예제를 살펴보자s.

도시 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이다.