题目描述 CSU 镇上有 ${n}$ 个商店，${n}$ 个商店有 ${m}$ 条双向小路相连，在这 ${n}$ 个商店里共有 ${k}$ 种不同商品，每个商店只有一种商品，每条路的权重都为 1。 现问你从每个商店出发，买够 ${k}$ 种商品中的 ${s}$ 种商品所需的最小代价，每个商店可以同时派出多个人买不同商品，买够即可。 输入格式 输入包含多组测试用例。 对于每一组输入包含四个数字 ${n, m, k, s}$（${1 \le n \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}$ 个商店的商品编号。 接下来 ${m}$ 行小路 ${(u,v)}$，${u \ne v}$，代表商店 ${u}$ 和 ${v}$ 之间有小路连接。 输出格式 输出 ${n}$ 个数字，第 ${i}$ 个数字代表从商店 ${i}$ 出发买够 ${s}$ 种商品所需的最小代价。 数据范围 ${1 \le n \le m \le 10^5}$，${1 \le s \le k \le \min(n,100)}$ 输入样例 5 5 4 3 1 2 4 3 2 1 2 2 3 3 4 4 1 4 5 7 6 3 2 1 2 3 3 2 2 1 1 2 2 3 3 4 2 5 5 6 6 7 输出样例 2 2 2 2 3 1 1 1 2 2 1 1