A6270. Welcome24ever 和袜子
编程题
普及+/提高
知识点
题目描述
Welcome24ever 已经长大且很独立。Welcome24ever 的妈妈决定离开 $m$ 天去度假。她已经为 Welcome24ever 准备了大量食物，留了一些钱，并把 Welcome24ever 的所有衣服都洗好了。
在她离开前的十分钟，她意识到还应该为每一天准备好详细的穿衣指令，指定每一天应该穿哪些袜子。他们家有点奇怪，所有的袜子都是编号的。具体来说，Welcome24ever 的每只袜子都被编号为 $1 \sim n$ 之间的一个整数。
因此，妈妈只需要为每一天写下两个整数 $l_i$ 和 $r_i$ —— 即第 $i$ 天要穿的两只袜子的编号（显然，$l_i$ 表示左脚，$r_i$ 表示右脚）。每只袜子都被涂成 $k$ 种颜色中的一种。
等妈妈离开后，Welcome24ever 发现如果完全照着说明来穿，Welcome24ever 在某些天会穿上不同颜色的袜子。这显然是妈妈匆忙造成的错误。Welcome24ever 是个聪明的孩子，而且巧合的是，Welcome24ever 刚好有 $k$ 罐不同颜色的油漆——每种颜色各一罐。
Welcome24ever 想给**部分袜子**重新上色，使得在每一天里，都能按照妈妈指定的袜子编号来穿，并且当天穿的两只袜子的颜色相同。由于接下来几天会非常忙，Welcome24ever 必须**现在就决定所有袜子的最终颜色**，之后不再更改。
最新的电脑游戏 Bota-3 刚刚发布，Welcome24ever 迫不及待想去玩。所以 Welcome24ever 希望你帮忙计算：
最少需要重新给多少只袜子涂色，才能保证对于所有 $m$ 天，都可以按照妈妈的指令，并且每天两只袜子的颜色一致？
在她离开前的十分钟，她意识到还应该为每一天准备好详细的穿衣指令，指定每一天应该穿哪些袜子。他们家有点奇怪，所有的袜子都是编号的。具体来说，Welcome24ever 的每只袜子都被编号为 $1 \sim n$ 之间的一个整数。
因此，妈妈只需要为每一天写下两个整数 $l_i$ 和 $r_i$ —— 即第 $i$ 天要穿的两只袜子的编号（显然，$l_i$ 表示左脚，$r_i$ 表示右脚）。每只袜子都被涂成 $k$ 种颜色中的一种。
等妈妈离开后，Welcome24ever 发现如果完全照着说明来穿，Welcome24ever 在某些天会穿上不同颜色的袜子。这显然是妈妈匆忙造成的错误。Welcome24ever 是个聪明的孩子，而且巧合的是，Welcome24ever 刚好有 $k$ 罐不同颜色的油漆——每种颜色各一罐。
Welcome24ever 想给**部分袜子**重新上色，使得在每一天里，都能按照妈妈指定的袜子编号来穿，并且当天穿的两只袜子的颜色相同。由于接下来几天会非常忙，Welcome24ever 必须**现在就决定所有袜子的最终颜色**，之后不再更改。
最新的电脑游戏 Bota-3 刚刚发布，Welcome24ever 迫不及待想去玩。所以 Welcome24ever 希望你帮忙计算：
最少需要重新给多少只袜子涂色，才能保证对于所有 $m$ 天，都可以按照妈妈的指令，并且每天两只袜子的颜色一致？
输入格式
第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 200000$，$0 \le m \le 200000$，$1 \le k \le 200000$），分别表示袜子的数量、天数以及可用的颜色种类数。
第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le k$），表示当前每只袜子的颜色，其中 $c_i$ 是编号为 $i$ 的袜子的颜色。
接下来的 $m$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i, r_i \le n$，$l_i \ne r_i$），表示第 $i$ 天应该穿的两只袜子的编号。
第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le k$），表示当前每只袜子的颜色，其中 $c_i$ 是编号为 $i$ 的袜子的颜色。
接下来的 $m$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i, r_i \le n$，$l_i \ne r_i$），表示第 $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
说明/提示
### 样例解释 #1
一种可行的方案是：把第 $1$ 只和第 $3$ 只袜子的颜色都改成第 $2$ 种颜色。这样三只袜子颜色都为 $2$，显然可以满足两天的要求，且重涂袜子数为 $2$，可以证明这是最优的。
### 样例解释 #2
按照当前颜色安排，两天中穿的袜子配对颜色都已经相同，因此不需要重新涂色，答案为 $0$。
一种可行的方案是：把第 $1$ 只和第 $3$ 只袜子的颜色都改成第 $2$ 种颜色。这样三只袜子颜色都为 $2$，显然可以满足两天的要求，且重涂袜子数为 $2$，可以证明这是最优的。
### 样例解释 #2
按照当前颜色安排，两天中穿的袜子配对颜色都已经相同，因此不需要重新涂色，答案为 $0$。