← 返回题目列表

Codeforces · 731/C

C. 袜子

中文机器翻译题面 查看原题

Arseniy 已经长大并且独立了。他的母亲决定让他独自呆 m 天,然后去度假。她准备了很多食物,留下了一些钱,还洗了阿尔谢尼所有的衣服。

在她离开前十分钟,她意识到准备在她缺席的每一天穿哪些特定衣服的指导也很有用。 Arseniy的家族有点奇怪所以所有的衣服都被列举了。例如,Arseniy 的 n 只袜子中的每只都被分配了一个从 1 到 n 的唯一整数。因此,他的母亲唯一要做的就是每天写下两个整数 li 和 ri - 第 i 天穿的袜子的索引(显然,li 代表左脚,ri 代表右脚)。每只袜子都涂有 k 种颜色中的一种。

当母亲离开时,Arseniy 注意到,根据指示,他有时会穿不同颜色的袜子。当然,这是仓促造成的可怕错误。 Arseniy 是一个聪明的男孩,并且由于某种神奇的巧合,他拥有 k 个装有颜料的罐子 - k 种颜色各一个。

Arseniy 想要以这样的方式重新绘制一些袜子,以便在每一 m 天他可以按照母亲的指示穿相同颜色的袜子。由于他这几天会很忙,所以没有时间改变袜子的颜色,所以他现在必须确定颜色。

新的电脑游戏 Bota-3 刚刚实现,Arseniy 迫不及待地想玩它。为了能够遵循母亲的指示并在 m 天的每一天穿相同颜色的袜子,需要改变颜色的袜子最少有多少只?

输入

输入的第一行包含三个整数 n、m 和 k (2 ≤ n ≤ 200 000, 0 ≤ m ≤ 200 000, 1 ≤ k ≤ 200 000)——分别是袜子的数量、天数和可用颜色的数量。

第二行包含 n 个整数 c1, c2, ..., cn (1 ≤ ci ≤ k) - Arseniy 袜子的当前颜色。

以下 m 行中的每一行都包含两个整数 li 和 ri (1 ≤ li, ri ≤ n, li ≠ ri) - Arseniy 在第 i 天应该穿的袜子的索引。

输出

打印一个整数 - 应该改变颜色的袜子的最少数量,以便能够遵守指示,并且不会因为看到不同颜色的袜子而让人发笑。

示例

输入 #1

3 2 3
1 2 3
1 2
2 3

输出 #1

2

输入 #2

3 2 2
1 1 2
1 2
2 1

输出 #2

0

注意

在第一个示例中,Arseniy 可以将第一只和第三只袜子重新绘制为第二种颜色。

在第二个示例中,无需更改任何颜色。