意大利数据中心由一组服务器(每台服务器颜色为绿色、白色或红色)以及一组连接它们的电线组成。每条线连接两个不同的服务器,并且两个服务器最多通过一根线连接。此外,数据中心是连接的,即有一种方法可以通过一系列线路在任意两个服务器之间传输信息。
为了评判所有参赛者提交的作品,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$$$ 年后的性能如何,因此您应该确定 SWERC 在 $$$k$$$ 年后数据中心的直径。数据中心的直径是任意两台服务器之间的最大距离,即两台服务器之间传输数据所需的最短电线数量。
输入
第一行包含三个整数 $$$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$$$ 线连接的两个服务器。
保证数据中心连通,每条线的端点清晰,且不存在重复线。
输出
打印 $$$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$$$。
在第三个示例中,一年后的数据中心如下:
又过了一年:
考虑突出显示的服务器。它们之间的距离为$$$3$$$,并且没有距离更大的服务器对,因此直径为$$$3$$$。