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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

1

输入样例 #2

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

输出样例 #2

2

输入样例 #3

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

输出样例 #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

说明

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 $ .

题意翻译

给定一张 $n$ 个点 $m$ 条边的无向连通图 $G_0 = (V_0, E_0)$，点集 $V_0$ 中编号为 $i$ 的点有颜色 $c_i(1\le c_i\le 3)$。 定义 $G_{i - 1} = (V_{i - 1}, E_{i - 1})$ 的拓张生成了 $G_i = (V_i, E_i)$，$G_i$ 定义如下： - 对每个点 $s\in V_{i - 1}$，$V_i$ 中都包含两个与 $s$ 颜色相同的点 $s_1, s_2$。$s_1, s_2$ 间的连边 $(s_1, s_2) \in E_i$。 - 对每条边 $(s, t) \in E_{i - 1}$：若 $s, t$ 颜色相同，则 $(s_1, t_1), (s_2, t_2) \in E_i$；反之 $(s_1, t_2), (s_2, t_1) \in E_i$。 定义一张无向连通图的直径为图上任意两点间最短路的最大长度。 给定 $k$，求 $G_k$ 的直径。 $2\le n\le 100, \ 0\le k\le 100, \ n - 1\le m\le n(n - 1) / 2$。