问题 4783 --袜子配对

4783: 袜子配对

时间限制: 1 Sec  内存限制: 128 MB
提交: 20  解决: 14
[提交][状态][命题人:]

题目描述

Z同学有n只袜子，编号1~n，袜子一共有k种颜色。Z同学的家长指定接下来m天里，他第i天穿的袜子编号是li和ri。但是Z同学不想穿不同颜色的袜子上学，他要通过改变袜子的颜色，让他每天都穿上同样颜色的两只袜子。Z同学每次可以改变一只袜子的颜色，最少需要改变几次？

输入

第一行输入包含三个整数n、m和k（2 ≤ n ≤ 200 000, 0 ≤ m ≤ 200 000, 1 ≤ k ≤ 200 000）——袜子的数量、天数和可用数量颜色分别。
第二行包含 n 个整数 c1, c2, ..., cn (1 ≤ ci ≤ k) — Z同学 袜子的当前颜色。
以下 m 行中的每一行包含两个整数 li 和 ri (1 ≤ li, ri ≤ n, li ≠ ri) — Z同学在第 i 天应该穿的袜子的索引。

输出

一个整数，Z同学至少需要改变多少只袜子的颜色
样例输入
Copy
3 2 3
1 2 3
1 2
2 3
样例输出
Copy
2

提示

样例2：

输入：

3 2 2
1 1 2
1 2
2 1

输出：

0


来源

ZZX2022 

[提交][状态]