说明

一个意大利数据中心由一组服务器组成，每台服务器被涂成绿色、白色或红色，并且有若干条线缆连接这些服务器。每条线缆连接两台不同的服务器，并且任意两台服务器之间至多有一条线缆。此外，数据中心是连通的，也就是说，任意两台服务器之间都存在一条通过若干线缆传递信息的路径。

为了评测所有参赛者的提交，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$ 年后 SWERC 数据中心的直径。数据中心的直径定义为任意两台服务器之间最短路径的最大值，即传递信息时需要经过的最少线缆数的最大值。

输入格式

第一行包含三个整数 $n$、$m$ 和 $k$（$2 \leq n \leq 100$，$n-1 \leq m \leq \frac{n(n-1)}{2}$，$0 \leq k \leq 100$），分别表示服务器数量、线缆数量和需要考虑的年数。

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

接下来的 $m$ 行，每行包含两个整数 $s_i$ 和 $t_i$（$1 \leq s_i, t_i \leq n$），表示第 $i$ 条线缆连接的两台服务器。

保证数据中心是连通的，每条线缆的两个端点不同，且没有重复的线缆。

输出格式

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

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

1

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

2

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

3

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

53

提示

在第一个样例中，意大利数据中心如下所示：

:::align{center} :::

任意两台服务器之间的距离都是 $1$，因此直径为 $1$。

在第二个样例中，初始意大利数据中心与第一个样例相同。

一年后得到如下结构（数字表示服务器的副本编号）：

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

在第三个样例中，一年后数据中心如下：

:::align{center} ::: 再过一年：

:::align{center} :::

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

由 ChatGPT 4.1 翻译