意大利数据中心由一组服务器（颜色分别为绿色、白色或红色）和连接它们的电线组成。每根电线连接两个不同的服务器，且任意两个服务器之间最多只有一根电线。此外，该数据中心是连通的，即可以通过一系列电线在任意两个服务器之间传输信息。

为了评估所有参赛者的提交，SWERC 拥有一个意大利数据中心。由于每年的参赛者人数都会翻倍，数据中心需要进行扩展以适应额外的负载。为了解决这个问题，SWERC 在前一年数据中心的基础上，通过以下步骤构建新的数据中心：

• 对于旧数据中心中的每个服务器 $s$，新数据中心包含两个与 $s$ 颜色相同的服务器 $s_1$ 和 $s_2$。在 $s_1$ 和 $s_2$ 之间连接一根电线。
• 对于旧数据中心中连接服务器 $s$ 和 $t$ 的每根电线：如果 $s$ 和 $t$ 颜色相同，则在新数据中心中连接 $s_1$ 和 $t_1$，并连接 $s_2$ 和 $t_2$；否则，在新数据中心中连接 $s_1$ 和 $t_2$，并连接 $s_2$ 和 $t_1$。

可以证明，如果旧数据中心是连通的，那么新数据中心也是连通的。

给定 SWERC 目前拥有的意大利数据中心，它包含 $n$ 个服务器（编号为 $1, 2, \dots, n$）和 $m$ 根连接它们的电线。组织方想知道 $k$ 年后他们的数据中心表现如何，因此你需要确定 $k$ 年后数据中心的直径。数据中心的直径是指任意两个服务器之间的最大距离，即在两个服务器之间传输信息所需的最短电线数量。

输入格式

第一行包含三个整数 $n, m$ 和 $k$ ($2 \le n \le 100, n-1 \le m \le n(n-1)/2, 0 \le k \le 100$) —— 服务器数量、电线数量以及需要考虑的年数。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 3$) —— $c_i$ 是服务器 $i$ 的颜色（其中 $1$ 代表绿色，$2$ 代表白色，$3$ 代表红色）。

接下来的 $m$ 行，每行包含两个整数 $s_i$ 和 $t_i$ ($1 \le s_i, t_i \le n$) —— 第 $i$ 根电线连接的两个服务器。

保证数据中心是连通的，每根电线的端点不同，且没有重复的电线。

输出格式

输出 $k$ 年后 SWERC 数据中心的直径。

样例

样例输入 1

3 3 0
1 2 3
1 2
2 3
3 1

样例输出 1

1

说明 1

意大利数据中心结构如下：

任意一对服务器之间的距离均为 $1$，因此直径为 $1$。

样例输入 2

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

样例输出 2

2

说明 2

初始的意大利数据中心与第一个样例相同。 一年后，我们得到如下结构（数字表示服务器对应的副本）：

考虑高亮显示的服务器。它们之间的距离为 $2$，且不存在距离更大的服务器对，因此直径为 $2$。

样例输入 3

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

样例输出 3

3

说明 3

一年后的数据中心结构如下：

再过一年：

考虑高亮显示的服务器。它们之间的距离为 $3$，且不存在距离更大的服务器对，因此直径为 $3$。

样例输入 4

8 14 100
3 3 2 2 1 2 2 1
2 7
1 5
7 8
4 6
2 8
1 8
2 6
6 7
1 6
1 4
3 5
1 3
4 5
5 7

样例输出 4

53