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

**意大利数据中心**

**题目描述：**
意大利数据中心由一系列服务器组成，每台服务器可以是绿色、白色或红色，以及连接它们的线缆。每根线缆连接两台不同的服务器，任意两台服务器之间最多只由一根线缆连接。此外，数据中心是连通的，即可以通过一系列线缆在任意两台服务器之间传输信息。

为了评判所有参赛者的提交，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的数据中心的直径。

**输入输出样例：**

**输入样例 #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
```

**说明：**
在第一个样例中，意大利数据中心的任意两台服务器之间的距离是 $ 1 $，因此直径是 $ 1 $。

在第二个样例中，初始的意大利数据中心是第一个样例中的数据中心。经过一年后，我们得到以下结果（数字表示服务器副本的编号）：

考虑高亮的服务器，它们之间的距离是 $ 2 $，并且没有其他服务器对的距离更远，所以直径是 $ 2 $。

在第三个样例**意大利数据中心** **题目描述：** 意大利数据中心由一系列服务器组成，每台服务器可以是绿色、白色或红色，以及连接它们的线缆。每根线缆连接两台不同的服务器，任意两台服务器之间最多只由一根线缆连接。此外，数据中心是连通的，即可以通过一系列线缆在任意两台服务器之间传输信息。 为了评判所有参赛者的提交，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的数据中心的直径。 **输入输出样例：** **输入样例 #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 ``` **说明：** 在第一个样例中，意大利数据中心的任意两台服务器之间的距离是 $ 1 $，因此直径是 $ 1 $。 在第二个样例中，初始的意大利数据中心是第一个样例中的数据中心。经过一年后，我们得到以下结果（数字表示服务器副本的编号）： 考虑高亮的服务器，它们之间的距离是 $ 2 $，并且没有其他服务器对的距离更远，所以直径是 $ 2 $。 在第三个样例