题目描述

Robocity 有 n 个十字路口，由双向道路连接。共有 m 条道路，并且所有十字路口彼此可达。

每个十字路口有一个等级，等级是从 1 到 k 的整数。任意一条道路连接的两个十字路口的等级一定不同。

城市领导计划进行改革。他们希望给十字路口重新分配等级，使得：

1. 每个等级仍然在 1 到 k 之间；
2. 由道路直接连接的两个十字路口等级不同；
3. 对于任意两个十字路口 u 和 v，都存在一条从 u 到 v 的路径，使得路径上任意相邻两个十字路口的等级在模 k 意义下相差 1。

形式化地，对于任意一对十字路口 $(u,v)$，应存在一个十字路口序列

满足：

• $p_1=u$；
• $p_l=v$；
• 对所有 $1\le i<l$，十字路口 $p_i$ 和 $p_{i+1}$ 之间有道路，并且它们的等级相差 1，或者一个等级为 1、另一个等级为 k。

Robocity 政府确信这样的等级分配一定存在，请你找出任意一种。

输入格式

第一行输入三个整数 n,m,k，分别表示十字路口数、道路数和等级数。

第二行输入 n 个整数：

其中 $c_i$ 是十字路口 i 原来的等级。

接下来 m 行，每行输入两个整数 u,v，表示一条连接 u 和 v 的道路。

保证不存在重边，并且整张图连通。

输出格式

输出 n 个整数：

其中 $d_i$ 表示十字路口 i 在新方案中的等级。

要求满足题目中的所有条件。

样例

样例输入：

4 4 4
1 2 3 1
1 2
1 3
2 3
3 4

样例输出：

4 3 2 1