CF2172M.Maximum Distance To Port

There are $n$ cities numbered from $1$ to $n$, connected by $m$ bidirectional roads, each exactly $1$ kilometer long. The road network forms a connected simple graph.

Each city produces exactly one of $k$ types of agricultural products, numbered from $1$ to $k$. City $1$ is the main port where all products must be delivered.

The government wants to estimate the worst-case transportation cost and time for exporting agricultural goods. To achieve this, they need to determine, for each product type, the longest among the shortest distances (in kilometers) from any city producing that product to the port city.

Your task is to compute this maximum shortest distance for each product type.

Figure 1: An illustration for sample input 2.

有 $n$ 座城市，编号从 $1$ 到 $n$，由 $m$ 条双向道路连接，每条道路长度恰好为 $1$ 千米。该道路网络构成一个连通的简单图。

每座城市恰好生产 $k$ 种农产品中的一种，农产品类型编号为 $1$ 至 $k$。城市 $1$ 是主要港口，所有农产品都必须运送到该城市。

政府希望估算农产品出口所需的最坏情况运输成本与时间。为此，他们需要针对每种农产品类型，计算所有生产该类型产品的城市到港口城市（即城市 $1$）的最短距离（单位：千米）中的最大值。

你的任务是：对每种农产品类型，计算该最大最短距离。

图 1：样例输入 2 的示意图。

The first line contains three integers $n$, $m$, and $k$, representing the number of cities, bidirectional roads, and product types, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, where $a_i$ is the product type produced by city $i$.

The $i$-th of the following $m$ lines contains two integers $u_i$ and $v_i$, representing that the $i$-th bidirectional road connects cities $u_i$ and $v_i$.

• $1 \leq n \leq 2 \times 10^{5}$
• $0 \leq m \leq 2 \times 10^{5}$
• $1 \leq k \leq n$
• $1 \leq a_i \leq k$
• $1 \leq u_i, v_i \leq n$
• The graph is connected and simple (no self-loops or multiple edges).
• Every product type from $1$ to $k$ is produced by at least one city.

第一行包含三个整数 $n$、$m$ 和 $k$，分别表示城市的数量、双向道路的数量以及产品类型的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示城市 $i$ 所生产的产品类型。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$，表示第 $i$ 条双向道路连接城市 $u_i$ 和 $v_i$。

• $1 \leq n \leq 2 \times 10^{5}$
• $0 \leq m \leq 2 \times 10^{5}$
• $1 \leq k \leq n$
• $1 \leq a_i \leq k$
• $1 \leq u_i, v_i \leq n$
• 图是连通的且为简单图（无自环、无重边）。
• 每一种从 $1$ 到 $k$ 的产品类型至少被一个城市生产。

Output $k$ integers in a single line. The $i$-th integer should be the maximum shortest distance (in kilometers) from any city producing product $i$ to the port city $1$.

在一行中输出 $k$ 个整数。其中第 $i$ 个整数应为任意生产产品 $i$ 的城市到港口城市 $1$ 的最大最短距离（单位：千米）。

Explanation of Example 2: Figure 1 illustrates this example. In this example, the port is the blue node. All goods of product type 5 are already in the port, so their transportation cost is 0. The transportation cost for product type 4 is higher. One city with product type 4 has a distance of 1 to the port, while another one has a distance 2. Therefore, the transportation cost is 2.

示例 2 的说明：图 1 展示了该示例。本例中，港口为蓝色节点。所有第 5 类产品均已位于港口，因此其运输成本为 0。第 4 类产品的运输成本更高：一个拥有第 4 类产品的城市到港口的距离为 1，另一个则为 2。因此，运输成本为 2。