有 $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$ 行中，第 $i$ 行包含两个整数 $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 的最大最短距离（以公里为单位）。

样例

输入 1

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

输出 1

1 0

输入 2

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

输出 2

1 3 2 2 0

说明

样例 2 的解释：图 1 展示了这个样例。在此样例中，港口是蓝色节点。所有产品类型 5 的货物已经在港口，因此它们的运输成本为 0。产品类型 4 的运输成本较高。其中一个生产产品类型 4 的城市到港口的距离为 1，而另一个距离为 2。因此，该产品的运输成本为 2。