题目描述

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

每座城市恰好生产 $k$ 种农产品中的一种，产品编号为 $1$ 到 $k$。$1$ 号城市是主港口，所有货物都必须运送到这里。

政府想要估算农产品出口在最坏情况下的运输开销与耗时。为此，对于每一种产品，需要求出：所有生产该产品的城市到港口的最短距离里的最大值（单位：千米）。

你的任务是，对每种产品，计算这个最大最短距离。

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

输入格式

第一行包含三个整数 $n,m,k$，分别代表城市数量、双向道路数量、产品种类数量。

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

接下来 $m$ 行，每行两个整数 $u_i,v_i$，代表第 $i$ 条双向道路连接城市 $u_i$ 和 $v_i$。

• $1 \le n \le 2 \times 10^{5}$
• $0 \le m \le 2 \times 10^{5}$
• $1 \le k \le n$
• $1 \le a_i \le k$
• $1 \le u_i, v_i \le n$
• 图是连通的简单图（无自环、无重边）
• $1$ 到 $k$ 的每一种产品，都至少有一座城市生产它。

输出格式

在一行内输出 $k$ 个整数。其中第 $i$ 个整数代表：所有生产第 $i$ 类产品的城市到港口 $1$ 的最短距离的最大值。

3 3 2
2 1 1
1 2
3 1
3 2

1 0

8 10 5
5 1 1 2 4 4 2 3
8 2
4 6
6 2
5 2
2 7
8 6
1 2
7 6
3 1
1 5

1 3 2 2 0

说明

样例 2 解释：图 1 为该样例的示意图。港口是蓝色节点。所有 5 类产品都在港口，因此运输代价为 $0$。4 类产品的运输代价更高：一座生产 4 类产品的城市到港口距离为 $1$，另一座距离为 $2$，因此运输代价是 $2$。

原题链接

原题链接