CF1776J.Italian Data Centers

An Italian data center consists of a set of servers, each colored green, white, or red, and a set of wires connecting them. Each wire connects two distinct servers and two servers are connected by at most one wire. Additionally, the data center is connected, i.e. there is a way to transmit information between any two servers through a sequence of wires.

To judge all of the contestant submissions, SWERC has an Italian data center. Since every year the number of contestants doubles, the data center needs to grow to adapt to the extra load. To address this, SWERC builds a new data center based on the previous year's one by following these steps:

• For each server $s$ in the old data center, the new data center contains two servers $s_1$ and $s_2$ of the same color as $s$. A wire is placed connecting the two servers $s_1$ and $s_2$.
• For each wire connecting servers $s$ and $t$ in the old data center: if $s$ and $t$ have the same color, then a wire is placed in the new data center connecting $s_1$ and $t_1$ and another wire connecting $s_2$ and $t_2$; otherwise, a wire is placed in the new data center connecting $s_1$ and $t_2$ and another one connecting $s_2$ and $t_1$.

One can show that if the old data center is connected than the new data center is also connected.

You are given the Italian data center that SWERC currently has, which contains $n$ servers (indexed by $1, \, 2, \, \dots, \, n$) and $m$ wires connecting them. The organization wants to know how good their data center will be after $k$ years, so you should determine the diameter of the data center SWERC will have in $k$ years. The diameter of the data center is the largest distance between any two servers, i.e. the shortest number of wires that have to be used to transmit something between the two servers.

一个意大利数据中心由一组服务器（每台服务器被涂成绿色、白色或红色）以及连接它们的一组网线组成。每条网线连接两台不同的服务器，且任意两台服务器之间至多有一条网线相连。此外，该数据中心是连通的，即任意两台服务器之间均存在一条由若干网线构成的路径，从而可实现信息传输。

为评判所有参赛选手的提交程序，SWERC 拥有一个意大利数据中心。由于每年参赛选手人数翻倍，该数据中心需不断扩容以应对额外负载。为此，SWERC 每年基于上一年的数据中心，按如下步骤构建新的数据中心：

• 对旧数据中心中的每台服务器 $s$，新数据中心中包含两台与其颜色相同的服务器 $s_1$ 和 $s_2$，并在 $s_1$ 与 $s_2$ 之间连接一条网线；
• 对旧数据中心中任意一条连接服务器 $s$ 与 $t$ 的网线：若 $s$ 与 $t$ 颜色相同，则在新数据中心中连接 $s_1$ 与 $t_1$，并另连接 $s_2$ 与 $t_2$；否则（即 $s$ 与 $t$ 颜色不同），则在新数据中心中连接 $s_1$ 与 $t_2$，并另连接 $s_2$ 与 $t_1$。

可以证明：若旧数据中心是连通的，则新数据中心也必然是连通的。

现给定 SWERC 当前拥有的意大利数据中心，其包含 $n$ 台服务器（编号为 $1,\,2,\,\dots,\,n$）以及 $m$ 条连接它们的网线。组织方希望了解其数据中心在 $k$ 年后的性能表现，因此你需要计算 $k$ 年后数据中心的直径。数据中心的直径定义为任意两台服务器之间的最大距离，即这两台服务器间信息传输所需经过的最短网线数目。

The first line contains three integers $n$, $m$ and $k$ ($2 \leq n \leq 100$, $n - 1 \leq m \leq n (n - 1) / 2$, $0 \leq k \leq 100$) — the number of servers, the number of wires, and the number of years to consider.

The second line contains $n$ integers $c_1, \, c_2, \, \dots, \, c_n$ ($1 \leq c_i \leq 3$) — $c_i$ is the color of server $i$ (where $1$ stands for green, $2$ for white and $3$ for red).

Each of the next $m$ lines contains two integers $s_i$ and $t_i$ ($1 \leq s_i, t_i \leq n$) — the two servers the $i$-th wire connects.

It is guaranteed that the data center is connected, the endpoints of each wire are distinct, and that there are no repeated wires.

第一行包含三个整数 $n$、$m$ 和 $k$（$2 \leq n \leq 100$，$n - 1 \leq m \leq 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$ 条网线所连接的两台服务器。

保证数据中心是连通的，每条网线的两个端点互不相同，且不存在重复的网线。

Print the diameter of SWERC's data center after $k$ years.

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

In the first sample, the Italian data center is the following:

The distance between any pair of servers is $1$ so the diameter is $1$.

In the second sample, the initial Italian data center is the one from the first sample.

After one year we obtain the following (where the numbers indicate which copy the server refers to):

Consider the highlighted servers. The distance between them is $2$ and there is no pair of servers with greater distance, so the diameter is $2$.

In the third sample, the data center after one year is the following:

After one more year:

Consider the highlighted servers. The distance between them is $3$ and there is no pair of servers with greater distance, so the diameter is $3$.

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

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

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

一年后，我们得到如下结构（其中数字表示该服务器所属的副本）：

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

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

再过一年后：

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