English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
## Note
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$.
某公司将在Byteland举办一场集市。Byteland中有$n$座城镇和$m$条双向道路。显然，通过道路可以从任意城镇到达其他任意城镇。
Byteland生产$k$种商品，每座城镇只生产一种商品。要举办一场集市，必须至少带来$s$种不同类型的商品。从城镇$u$将商品运送到城镇$v$的成本为$d(u, v)$枚硬币，其中$d(u, v)$是$u$到$v$的最短路径长度（路径长度定义为路径中的道路数量）。
主办方将承担所有交通费用，但他们可以选择从哪些城镇运送商品。现在他们希望计算在每座城镇举办集市所需的最小交通费用。
输入的第一行包含四个整数$n$，$m$，$k$，$s$（$1 \leq n \leq 10^5$，$0 \leq m \leq 10^5$，$1 \leq s \leq k \leq \min(n, 100)$）——分别表示城镇数量、道路数量、不同商品类型数量以及举办集市所需的不同商品类型数量。
接下来一行包含$n$个整数$a_1, a_2, \dots, a_n$（$1 \leq a_i \leq k$），其中$a_i$表示第$i$座城镇生产的商品类型。保证$1$到$k$之间的每个整数在$a_i$中至少出现一次。
接下来$m$行描述道路。每条道路由两个整数$u$ $v$（$1 \leq u, v \leq n$，$u \neq v$）描述，表示连接这两座城镇的道路。保证任意两座城镇之间至多有一条道路，且任意城镇均可通过道路到达其他任意城镇。
请输出$n$个数，第$i$个数表示在第$i$座城镇举办集市所需的最小交通费用（以硬币为单位）。数字之间用空格分隔。
让我们看第一个样例。
要在城镇$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$。
## Input
输入的第一行包含四个整数$n$，$m$，$k$，$s$（$1 \leq n \leq 10^5$，$0 \leq m \leq 10^5$，$1 \leq s \leq k \leq \min(n, 100)$）——分别表示城镇数量、道路数量、不同商品类型数量以及举办集市所需的不同商品类型数量。接下来一行包含$n$个整数$a_1, a_2, \dots, a_n$（$1 \leq a_i \leq k$），其中$a_i$表示第$i$座城镇生产的商品类型。保证$1$到$k$之间的每个整数在$a_i$中至少出现一次。接下来$m$行描述道路。每条道路由两个整数$u$ $v$（$1 \leq u, v \leq n$，$u \neq v$）描述，表示连接这两座城镇的道路。保证任意两座城镇之间至多有一条道路，且任意城镇均可通过道路到达其他任意城镇。
## Output
请输出$n$个数，第$i$个数表示在第$i$座城镇举办集市所需的最小交通费用（以硬币为单位）。数字之间用空格分隔。
[samples]
## Note
让我们看第一个样例。
要在城镇$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$。
Let $ G = (V, E) $ be an undirected, unweighted, connected graph with $ |V| = n $, $ |E| = m $.
Let $ a: V \to \{1, 2, \dots, k\} $ be a function assigning to each town $ v \in V $ a good type $ a_v $.
Let $ d(u, v) $ denote the shortest path distance (number of edges) between nodes $ u $ and $ v $ in $ G $.
For each town $ i \in V $, define the cost $ C(i) $ as the minimum total distance required to collect at least $ s $ distinct good types, where goods may be sourced from any subset of towns, and the cost of sourcing a good from town $ u $ to town $ i $ is $ d(i, u) $.
**Objective:**
For each $ i \in V $, compute:
$$
C(i) = \min_{\substack{S \subseteq V \\ |\{a_u : u \in S\}| \geq s}} \sum_{u \in S} d(i, u)
$$
**Constraints:**
- $ 1 \leq n, m \leq 10^5 $, $ 1 \leq s \leq k \leq \min(n, 100) $
- $ a $ is surjective onto $ \{1, \dots, k\} $
- Graph $ G $ is connected and unweighted
**Note:** For efficiency, for each good type $ t \in \{1, \dots, k\} $, define $ D_t(i) = \min\{ d(i, u) : a_u = t \} $, i.e., the shortest distance from town $ i $ to any town producing good type $ t $.
Then, $ C(i) $ is the sum of the $ s $ smallest values among $ \{ D_1(i), D_2(i), \dots, D_k(i) \} $.
**Final Formulation:**
For each $ i \in \{1, \dots, n\} $:
$$
C(i) = \sum_{j=1}^{s} \text{smallest}_j \left( \min_{u: a_u = t} d(i, u) \right)_{t=1}^{k}
$$
API Response (JSON)
{
"problem": {
"name": "A. Fair",
"description": {
"content": "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$",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF986A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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.\n\nThere are $k$...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "某公司将在Byteland举办一场集市。Byteland中有$n$座城镇和$m$条双向道路。显然，通过道路可以从任意城镇到达其他任意城镇。\n\nByteland生产$k$种商品，每座城镇只生产一种商品。要举办一场集市，必须至少带来$s$种不同类型的商品。从城镇$u$将商品运送到城镇$v$的成本为$d(u, v)$枚硬币，其中$d(u, v)$是$u$到$v$的最短路径长度（路径长度定义为路径中的道路...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ G = (V, E) $ be an undirected, unweighted, connected graph with $ |V| = n $, $ |E| = m $. \nLet $ a: V \\to \\{1, 2, \\dots, k\\} $ be a function assigning to each town $ v \\in V $ a good type $ a_v...",
"is_translate": false,
"language": "Formal"
}
]
}