Arseniy is already grown-up and independent. His mother decided to leave him alone for m days and left on a vacation. She have prepared a lot of food, left some money and washed all Arseniy's clothes. 

Ten minutes before her leave she realized that it would be also useful to prepare instruction of which particular clothes to wear on each of the days she will be absent. Arseniy's family is a bit weird so all the clothes is enumerated. For example, each of Arseniy's n socks is assigned a unique integer from 1 to n. Thus, the only thing his mother had to do was to write down two integers l_{i} and r_{i} for each of the days — the indices of socks to wear on the day i (obviously, l_{i} stands for the left foot and r_{i} for the right). Each sock is painted in one of k colors.

When mother already left Arseniy noticed that according to instruction he would wear the socks of different colors on some days. Of course, that is a terrible mistake cause by a rush. Arseniy is a smart boy, and, by some magical coincidence, he posses k jars with the paint — one for each of k colors.

Arseniy wants to repaint some of the socks in such a way, that for each of m days he can follow the mother's instructions and wear the socks of the same color. As he is going to be very busy these days he will have no time to change the colors of any socks so he has to finalize the colors now.

The new computer game Bota-3 was just realised and Arseniy can't wait to play it. What is the minimum number of socks that need their color to be changed in order to make it possible to follow mother's instructions and wear the socks of the same color during each of m days.


-----Input-----

The first line of input contains three integers n, m and k (2 ≤ n ≤ 200 000, 0 ≤ m ≤ 200 000, 1 ≤ k ≤ 200 000) — the number of socks, the number of days and the number of available colors respectively.

The second line contain n integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ k) — current colors of Arseniy's socks.

Each of the following m lines contains two integers l_{i} and r_{i} (1 ≤ l_{i}, r_{i} ≤ n, l_{i} ≠ r_{i}) — indices of socks which Arseniy should wear during the i-th day.


-----Output-----

Print one integer — the minimum number of socks that should have their colors changed in order to be able to obey the instructions and not make people laugh from watching the socks of different colors.


-----Examples-----
Input
3 2 3
1 2 3
1 2
2 3

Output
2

Input
3 2 2
1 1 2
1 2
2 1

Output
0



-----Note-----

In the first sample, Arseniy can repaint the first and the third socks to the second color.

In the second sample, there is no need to change any colors.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Spanning trees

Graph algorithms

Graph traversal

Greedy algorithms


Solutions:
def main():
	from collections import defaultdict, Counter
	(n, m, k) = map(int, input().split())
	n += 1
	cc = [0, *map(int, input().split())]
	l = list(range(n))
	for _ in range(m):
		(a, b) = map(int, input().split())
		(u, v) = (a, b)
		while u != l[u]:
			u = l[u]
		while v != l[v]:
			v = l[v]
		if u > v:
			l[u] = v
			while a != v:
				(a, l[a]) = (l[a], v)
		elif u < v:
			l[v] = u
			while b != u:
				(b, l[b]) = (l[b], u)
	groups = defaultdict(Counter)
	for (i, g) in enumerate(l):
		if i != g:
			l[i] = g = l[g]
			groups[g][cc[i]] += 1
	for (g, v) in groups.items():
		v[cc[g]] += 1
	print(sum((sum(v.values()) - v.most_common(1)[0][1] for v in groups.values())))
main()


(n, m, k) = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
num = 0
clusters = {}
socks = {}
for i in range(m):
	(l, r) = [int(i) for i in input().split()]
	if l not in socks and r not in socks:
		socks[l] = num
		socks[r] = num
		clusters[num] = [l, r]
		num += 1
	elif l not in socks and r in socks:
		socks[l] = socks[r]
		clusters[socks[r]].append(l)
	elif l in socks and r not in socks:
		socks[r] = socks[l]
		clusters[socks[l]].append(r)
	elif socks[r] != socks[l]:
		clusters[socks[l]] += clusters[socks[r]]
		temp = socks[r]
		for sock in clusters[socks[r]]:
			socks[sock] = socks[l]
		clusters.pop(temp)
to_paint = 0
for i in clusters:
	colors = {}
	ma = 0
	for sock in set(clusters[i]):
		k = c[sock - 1]
		if k in colors:
			colors[k] += 1
		else:
			colors[k] = 1
		if colors[k] > ma:
			ma = colors[k]
	to_paint += len(clusters[i]) - ma
print(to_paint)


def main():
	from collections import defaultdict, Counter
	(n, m, k) = map(int, input().split())
	n += 1
	cc = [0, *map(int, input().split())]
	l = list(range(n))

	def find(x):
		while x != l[x]:
			x = l[x]
		return x
	for _ in range(m):
		(a, b) = map(int, input().split())
		(u, v) = (find(a), find(b))
		if u > v:
			l[u] = v
			while a != v:
				(a, l[a]) = (l[a], v)
		elif u < v:
			l[v] = u
			while b != u:
				(b, l[b]) = (l[b], u)
	groups = defaultdict(list)
	for (i, c) in enumerate(cc):
		l[i] = i = find(i)
		groups[i].append(c)
	for v in groups.values():
		n -= Counter(v).most_common(1)[0][1] if len(l) > 1 else 1
	print(n)
main()


from collections import defaultdict
(n, m, k) = [int(x) for x in input().split()]
c = [0] + [int(x) for x in input().split()]
g = defaultdict(lambda : [])
for i in range(m):
	(l, r) = [int(x) for x in input().split()]
	g[l].append(r)
	g[r].append(l)
done = [0] * (1 + n)
ans = 0
for i in range(n):
	i += 1
	if done[i]:
		continue
	q = [i]
	p = 0
	mn = set([i])
	mcx = defaultdict(lambda : 0)
	while p != len(q):
		t = q[p]
		p += 1
		if done[t]:
			continue
		done[t] = 1
		mcx[c[t]] += 1
		mn.add(t)
		for ne in g[t]:
			q.append(ne)
	fcol = None
	maxn = -1
	for (col, num) in mcx.items():
		if num >= maxn:
			maxn = num
			fcol = col
	if fcol:
		for ob in mn:
			if c[ob] != fcol and len(g[ob]) > 0:
				c[ob] = fcol
				ans += 1
print(ans)


import collections

class UnionFind:

	def __init__(self, size):
		self.size = size
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			if self.table[self.table[x]] >= 0:
				self.table[x] = self.table[self.table[x]]
			x = self.table[x]
		return x

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] >= self.table[s2]:
				self.table[s1] += self.table[s2]
				self.table[s2] = s1
			else:
				self.table[s2] += self.table[s1]
				self.table[s1] = s2
		return self.table[s1]

	def count_group(self):
		count = 0
		for i in range(self.size):
			if self.table[i] < 0:
				count += 1
		return count
(n, m, k) = map(int, input().split())
c = [0] + list(map(int, input().split()))
uf = UnionFind(n + 1)
use = [False] * (n + 1)
for i in range(m):
	(li, ri) = map(int, input().split())
	uf.union(li, ri)
	use[li] = True
	use[ri] = True
groups = {}
for i in range(1, n + 1):
	if not use[i]:
		continue
	g = uf.find(i)
	if g not in groups:
		groups.update({g: collections.defaultdict(int)})
	groups[g][c[i]] += 1
total = 0
for g in groups.values():
	total += sum(g.values()) - max(g.values())
print(total)


def main():
	from collections import Counter
	(n, m, _) = map(int, input().split())
	cc = list(map(int, input().split()))
	(pairs, avail) = ([[] for _ in range(n)], [True] * n)
	for _ in range(m):
		(a, b) = map(int, input().split())
		pairs[a - 1].append(b - 1)
		pairs[b - 1].append(a - 1)
	for (a, f) in enumerate(avail):
		if f:
			(stack, cnt, avail[a]) = ([a], Counter(), False)
			while stack:
				a = stack.pop()
				cnt[cc[a]] += 1
				for b in pairs[a]:
					if avail[b]:
						avail[b] = False
						stack.append(b)
			n -= cnt.most_common(1)[0][1]
	print(n)

def __starting_point():
	main()
__starting_point()


(n, m, k) = list(map(int, input().split()))
c = [int(x) - 1 for x in input().split()]
adj = [[] for _ in range(n)]
for _ in range(m):
	(l, r) = list(map(int, input().split()))
	adj[l - 1].append(r - 1)
	adj[r - 1].append(l - 1)
vis = [0] * n
ans = 0
for i in range(n):
	if vis[i] == 1:
		continue
	(arr, cur) = ([i], 0)
	while cur < len(arr):
		v = arr[cur]
		vis[v] = 1
		cur += 1
		for nv in adj[v]:
			if vis[nv] == 0:
				arr.append(nv)
				vis[nv] = 1
	d = {}
	for v in arr:
		d[c[v]] = d.get(c[v], 0) + 1
	ans += len(arr) - max(d.values())
print(ans)


import sys
(n, m, k) = [int(x) for x in sys.stdin.readline().replace('\n', '').split(' ')]
c = [int(x) for x in sys.stdin.readline().replace('\n', '').split(' ')]
socks = [[] for _ in range(n)]
for i in range(m):
	(l, r) = [int(x) - 1 for x in sys.stdin.readline().replace('\n', '').split(' ')]
	socks[r] += [l]
	socks[l] += [r]
visited = [False for _ in range(n)]
forest = {}
for (i, v) in enumerate(visited):
	if v:
		continue
	visited[i] = True
	queue = [(i, i)]
	forest[i] = {'nodes': [i], 'colours': {c[i]: 1}}
	while len(queue) != 0:
		(representant, current) = queue.pop()
		for node in socks[current]:
			if not visited[node]:
				queue += [(representant, node)]
				forest[representant]['nodes'] += [node]
				if c[node] in forest[representant]['colours']:
					forest[representant]['colours'][c[node]] += 1
				else:
					forest[representant]['colours'][c[node]] = 1
				visited[node] = True
total = 0
for key in forest:
	maximun = 0
	for i in forest[key]['colours']:
		if forest[key]['colours'][i] > maximun:
			maximun = forest[key]['colours'][i]
	total += len(forest[key]['nodes']) - maximun
sys.stdout.write(str(total))


(n, m, k) = map(int, input().split())
c = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(m):
	(l, r) = map(int, input().split())
	g[l - 1].append(r - 1)
	g[r - 1].append(l - 1)
v = [-1] * n
o = 0
for i in range(n):
	if v[i] == -1:
		s = [i]
		v[i] = 1
		q = {}
		while s:
			x = s.pop()
			if c[x] not in q:
				q[c[x]] = 0
			q[c[x]] += 1
			for j in g[x]:
				if v[j] == -1:
					v[j] = 1
					s.append(j)
		(r, k) = (0, 0)
		for b in q:
			k = max(k, q[b])
			r += q[b]
		o += r - k
print(o)


import math
import time
from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
from queue import PriorityQueue
import sys

class Graph:

	def __init__(self, n):
		self.graph = defaultdict(lambda : [])
		self.vertices = n
		self.edges = 0
		self.toposorted = []

	def addEdge(self, a, b):
		self.graph[a].append(b)
		self.edges += 1

	def cycleUntill(self, visited, curr, parent):
		visited[curr] = True
		for i in self.graph[curr]:
			if not visited[i]:
				if self.cycleUntill(visited, i, curr):
					return True
			elif i != parent:
				return True
		return False

	def cycle(self):
		n = self.vertices
		visited = [False] * (n + 2)
		for i in range(1, n + 1):
			if not visited[i]:
				if self.cycleUntill(visited, i, -1):
					return True
		return False

	def topologicalSort(self):
		in_degree = [0] * (self.vertices + 10)
		for i in self.graph:
			for j in self.graph[i]:
				in_degree[j] += 1
		queue = deque()
		for i in range(1, self.vertices + 1):
			if in_degree[i] == 0:
				queue.append(i)
		cnt = 0
		while queue:
			u = queue.popleft()
			self.toposorted.append(u)
			for i in self.graph[u]:
				in_degree[i] -= 1
				if in_degree[i] == 0:
					queue.append(i)
			cnt += 1
		if cnt != self.vertices:
			return False
		else:
			return True

	def connected(self):
		visited = [False] * (self.vertices + 2)
		ans = []
		for i in range(1, self.vertices + 1):
			if not visited[i]:
				comp = []
				q = deque()
				visited[i] = True
				q.append(i)
				while len(q) > 0:
					temp = q.popleft()
					comp.append(temp)
					for j in self.graph[temp]:
						if not visited[j]:
							visited[j] = True
							q.append(j)
				ans.append(comp)
		return ans
(n, m, k) = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
g = Graph(n)
for _ in range(m):
	(l, r) = map(int, stdin.readline().split())
	g.addEdge(l, r)
	g.addEdge(r, l)
connected = g.connected()
ans = 0
for i in connected:
	color = [0] * len(i)
	for j in range(len(i)):
		color[j] = a[i[j] - 1]
	count = Counter(color)
	ans += len(i) - count.most_common(1)[0][1]
print(ans)


from collections import deque
import sys
input = sys.stdin.buffer.readline
(n, m, k) = map(int, input().split())
colors = list(map(int, input().split()))
adj = [[] for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	adj[u].append(v)
	adj[v].append(u)
total_change = 0
visited = [0] * n
for i in range(n):
	if not visited[i]:
		curr_comp = []
		s = deque([i])
		while s:
			curr = s[-1]
			if not visited[curr]:
				for neighbor in adj[curr]:
					s.append(neighbor)
				visited[curr] = 1
				curr_comp.append(curr)
			else:
				s.pop()
		total = len(curr_comp)
		most = {}
		for a in curr_comp:
			if colors[a] in most:
				most[colors[a]] += 1
			else:
				most[colors[a]] = 1
		total_change += total - max(most.values())
print(total_change)


(n, m, k) = map(int, input().split())
socks = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)
component = [None] * n
cur_comp = 0
for i in range(n):
	if component[i] is None:
		todo = [i]
		while todo:
			xi = todo.pop()
			component[xi] = cur_comp
			for neighbour in adj[xi]:
				if component[neighbour] is None:
					todo.append(neighbour)
		cur_comp += 1
components = [[] for _ in range(cur_comp)]
for (v, c) in enumerate(component):
	components[c].append(v)
out = 0
for c in components:
	counter = {}
	for v in c:
		if socks[v] not in counter:
			counter[socks[v]] = 0
		counter[socks[v]] += 1
	out += len(c) - max(counter.values())
print(out)


from itertools import permutations as perm
from collections import *
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n, m, k) = gil()
color = gil()
adj = [[] for _ in range(n)]
for _ in range(m):
	(l, r) = gil()
	l -= 1
	r -= 1
	adj[l].append(r)
	adj[r].append(l)
ans = 0
vis = [0] * n
for i in range(n):
	if vis[i]:
		continue
	stack = [i]
	dfs = []
	while stack:
		p = stack.pop()
		if vis[p]:
			continue
		dfs.append(p)
		vis[p] = 1
		for c in adj[p]:
			if not vis[c]:
				stack.append(c)
	for i in range(len(dfs)):
		dfs[i] = color[dfs[i]]
	ans += len(dfs) - max(Counter(dfs).values())
print(ans)


from collections import deque, defaultdict

def BFS(graph, source, visited):
	n = len(graph)
	queue = deque()
	queue.append(source)
	visited[source] = True
	while len(queue) > 0:
		u = queue.popleft()
		yield u
		for v in graph[u]:
			if not visited[v]:
				visited[v] = True
				queue.append(v)

def get_components(adjacency_list, n):
	visited = [False] * n
	for i in range(n):
		if not visited[i]:
			yield list(BFS(adjacency_list, i, visited))

def __starting_point():
	(n, m, k) = list(map(int, input().split()))
	colours = [int(x) - 1 for x in input().split()]
	adjacency_list = [[] for _ in range(n)]
	for _ in range(m):
		(l, r) = (int(x) - 1 for x in input().split())
		adjacency_list[l].append(r)
		adjacency_list[r].append(l)
	components = get_components(adjacency_list, n)
	changes = 0
	for component in components:
		colour_counts = defaultdict(int)
		max_count = 0
		for sock in component:
			counter = colour_counts[colours[sock]] + 1
			colour_counts[colours[sock]] = counter
			if counter > max_count:
				max_count = counter
		changes += len(component) - max_count
	print(changes)
__starting_point()


import sys
input = sys.stdin.readline
from collections import defaultdict

class Unionfind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [1] * n

	def root(self, x):
		p = x
		while not self.par[p] < 0:
			p = self.par[p]
		while x != p:
			tmp = x
			x = self.par[x]
			self.par[tmp] = p
		return p

	def unite(self, x, y):
		(rx, ry) = (self.root(x), self.root(y))
		if rx == ry:
			return False
		if self.rank[rx] < self.rank[ry]:
			(rx, ry) = (ry, rx)
		self.par[rx] += self.par[ry]
		self.par[ry] = rx
		if self.rank[rx] == self.rank[ry]:
			self.rank[rx] += 1

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def count(self, x):
		return -self.par[self.root(x)]
(n, m, k) = list(map(int, input().split()))
c = list(map(int, input().split()))
uf = Unionfind(n)
for _ in range(m):
	(l, r) = list(map(int, input().split()))
	uf.unite(l - 1, r - 1)
cnt = defaultdict(dict)
for i in range(n):
	r = uf.root(i)
	if c[i] not in cnt[r]:
		cnt[r][c[i]] = 1
	else:
		cnt[r][c[i]] += 1
ans = 0
for r in list(cnt.keys()):
	l = list(cnt[r].values())
	ans += sum(l) - max(l)
print(ans)


(n, m, k) = map(int, input().split())
c = list(map(int, input().split()))
c = list(map(lambda x: x - 1, c))
adj = [[] for _ in range(n)]
edges = list((list(map(int, input().split())) for _ in range(m)))
for (u, v) in edges:
	u -= 1
	v -= 1
	adj[u].append(v)
	adj[v].append(u)
vis = [0] * n
res = 0
for i in range(n):
	if vis[i] == 1:
		continue
	(arr, curr) = ([i], 0)
	while curr < len(arr):
		u = arr[curr]
		vis[u] = 1
		curr += 1
		for v in adj[u]:
			if vis[v] == 0:
				arr.append(v)
				vis[v] = 1
	d = {}
	for j in arr:
		d[c[j]] = d.get(c[j], 0) + 1
	res += len(arr) - max(d.values())
print(res)


class UnionFind:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.rank = [0 for i in range(n)]

	def find(self, x):
		if self.parent[x] is x:
			return x
		else:
			self.parent[x] = self.find(self.parent[x])
			return self.parent[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			self.parent[x] = y
		else:
			self.parent[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
import sys, threading

class graph:

	def __init__(self, n):
		self.size = n
		self.adj = [[] for _ in range(n)]

	def add_edge(self, u, v):
		self.adj[u].append(v)
		self.adj[v].append(u)

	def DFS(self, node):
		self.visited[node] = True
		subg = [node]
		for edge in self.adj[node]:
			if not self.visited[edge]:
				subg.extend(self.DFS(edge))
		return subg

	def components(self):
		self.visited = [False] * self.size
		self.components = []
		for node in range(self.size):
			if self.visited[node] is False:
				self.components.append(self.DFS(node))
		return self.components
(n, m, k) = [int(x) for x in input().split()]
uf = UnionFind(n)
color = [int(x) for x in input().split()]
for _ in range(m):
	(u, v) = [int(x) for x in input().split()]
	uf.union(u - 1, v - 1)
collection = [[] for i in range(n)]
for i in range(n):
	collection[uf.find(i)].append(i)
ans = 0
for sock_set in collection:
	if not sock_set:
		continue
	count = {}
	set_max = 1
	for sock in sock_set:
		try:
			count[color[sock]] += 1
			set_max = max(count[color[sock]], set_max)
		except:
			count[color[sock]] = 1
	ans += len(sock_set) - set_max
print(ans)


import sys
from math import sqrt, gcd, ceil, log
from collections import defaultdict, Counter, deque
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))

def main():
	(n, m, k) = read()
	col = [0] + read()
	adj = defaultdict(list)
	for i in range(m):
		(u, v) = read()
		adj[u].append(v)
		adj[v].append(u)
	visited = defaultdict(int)

	def dfs(node):
		most_col = Counter()
		components = []
		most_col[col[node]] += 1
		stk = [node]
		visited[node] += 1
		while stk:
			par = stk.pop()
			components.append(par)
			for child in adj[par]:
				if not visited[child]:
					most_col[col[child]] += 1
					visited[child] = 1
					stk.append(child)
		maxi = most_col.most_common()[0][0]
		ans = 0
		for i in components:
			ans += col[i] != maxi
		return ans
	ans = 0
	for i in range(1, n + 1):
		if not visited[i]:
			ans += dfs(i)
	print(ans)
main()


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
tr = [[] for i in range(n)]
for i in range(m):
	(l, r) = map(int, input().split())
	tr[l - 1].append(r - 1)
	tr[r - 1].append(l - 1)
visited = [False for i in range(n)]
ans = 0
for i in range(n):
	if visited[i]:
		continue
	s = [i]
	visited[i] = True
	qeue = {}
	while s:
		x = s.pop()
		if a[x] not in qeue:
			qeue[a[x]] = 0
		qeue[a[x]] += 1
		for j in tr[x]:
			if visited[j]:
				continue
			visited[j] = True
			s.append(j)
	(neu, maxi) = (0, 0)
	for e in qeue:
		maxi = max(maxi, qeue[e])
		neu += qeue[e]
	ans += neu - maxi
print(ans)


from collections import defaultdict, deque
from sys import stdin, stdout

def dfs(visited, node_idx, graph, color_count, sock_colors):
	visited[node_idx] = True
	color_count[sock_colors[node_idx]] += 1
	count = 1
	for nbor_idx in graph[node_idx]:
		if not visited[nbor_idx]:
			count += dfs(visited, nbor_idx, graph, color_count, sock_colors)
	return count

def bfs(visited, idx, graph, color_count, sock_counts):
	q = deque()
	q.append(idx)
	count = 0
	while len(q) != 0:
		_next = q.popleft()
		if visited[_next]:
			continue
		visited[_next] = True
		color_count[sock_colors[_next]] += 1
		count += 1
		for nbor_idx in graph[_next]:
			q.append(nbor_idx)
	return count

def disjoint(graph, sock_colors):
	total = 0
	visited = [False] * len(graph)
	for (idx, nbors) in enumerate(graph):
		color_count = defaultdict(int)
		if not visited[idx]:
			size = bfs(visited, idx, graph, color_count, sock_colors)
			total += size - max(color_count.values())
	return total
(num_socks, num_days, num_colors) = list(map(int, stdin.readline().split(' ')))
sock_colors = list(map(int, stdin.readline().split(' ')))
graph = [[] for i in range(num_socks)]
for i in range(num_days):
	(a, b) = list(map(int, stdin.readline().split(' ')))
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
ans = disjoint(graph, sock_colors)
print(ans)


def dfs(v, visited, edges, colors):
	st = [v]
	visited.add(v)
	comp = []
	cols = dict()
	while st:
		ver = st.pop()
		comp.append(colors[ver])
		if ver in edges:
			for i in edges[ver]:
				if i not in visited:
					st.append(i)
					visited.add(i)
	for i in comp:
		if i not in cols:
			cols[i] = 1
		else:
			cols[i] += 1
	max_c = 0
	for i in cols:
		if cols[i] > max_c:
			max_c = cols[i]
	return len(comp) - max_c
(n, m, k) = [int(x) for x in input().split()]
colors = {i + 1: int(x) for (i, x) in enumerate(input().split())}
edges = dict()
for i in range(m):
	(v1, v2) = [int(x) for x in input().split()]
	if v1 in edges:
		edges[v1].append(v2)
	else:
		edges[v1] = [v2]
	if v2 in edges:
		edges[v2].append(v1)
	else:
		edges[v2] = [v1]
visited = set()
answer = 0
for i in range(1, n + 1):
	if i not in visited:
		answer += dfs(i, visited, edges, colors)
print(answer)


from collections import deque, defaultdict

def BFS(graph, source, visited, colours):
	colour_counts = defaultdict(int)
	max_count = 0
	total = 0
	n = len(graph)
	queue = deque()
	queue.append(source)
	visited[source] = True
	while len(queue) > 0:
		u = queue.popleft()
		total += 1
		counter = colour_counts[colours[u]] + 1
		colour_counts[colours[u]] = counter
		if counter > max_count:
			max_count = counter
		for v in graph[u]:
			if not visited[v]:
				visited[v] = True
				queue.append(v)
	return (total, max_count)

def get_totals_and_maxcounts(adjacency_list, n, colours):
	visited = [False] * n
	for i in range(n):
		if not visited[i]:
			yield BFS(adjacency_list, i, visited, colours)
(n, m, k) = map(int, input().split())
colours = [int(x) - 1 for x in input().split()]
adjacency_list = [[] for _ in range(n)]
for _ in range(m):
	(l, r) = (int(x) - 1 for x in input().split())
	adjacency_list[l].append(r)
	adjacency_list[r].append(l)
changes = 0
for (total, max_count) in get_totals_and_maxcounts(adjacency_list, n, colours):
	changes += total - max_count
print(changes)


(N, M, K) = map(int, input().split())
Colours = list(map(int, input().split()))
import collections
from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		group_members = defaultdict(list)
		for member in range(self.n):
			group_members[self.find(member)].append(member)
		return group_members

	def __str__(self):
		return '\n'.join((f'{r}: {m}' for (r, m) in self.all_group_members().items()))
uf = UnionFind(N)
for i in range(0, M):
	(A, B) = map(int, input().split())
	uf.union(A - 1, B - 1)
D = list(uf.all_group_members().values())
count = 0
for i in range(0, len(D)):
	Vectors = []
	cnt = collections.Counter()
	for j in range(0, len(D[i])):
		Vectors.append(Colours[D[i][j]])
	for word in Vectors:
		cnt[word] += 1
	count += len(Vectors) - cnt.most_common(1)[0][1]
print(count)


def find(node):
	while p[node] != node:
		p[node] = p[p[node]]
		node = p[node]
	return node

def union(n1, n2):
	p1 = find(n1)
	p2 = find(n2)
	if p1 != p2:
		p[p1] = p2
(n, m, k) = map(int, input().split())
socks = list(map(int, input().split()))
p = [i for i in range(n)]
used = set()
for i in range(m):
	(a, b) = map(int, input().split())
	union(a - 1, b - 1)
	used.add(a - 1)
	used.add(b - 1)
cc = {}
for i in used:
	x = find(i)
	if x not in cc:
		cc[x] = []
		cc[x].append(socks[i])
	else:
		cc[x].append(socks[i])
ans = 0
for each in cc.values():
	each.sort()
	cnt = 1
	l = len(each)
	mx = 1
	for i in range(l - 1):
		if each[i + 1] != each[i]:
			mx = max(mx, cnt)
			cnt = 1
		else:
			cnt += 1
	mx = max(cnt, mx)
	ans += l - mx
print(ans)


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
int1 = lambda x: int(x) - 1

def input():
	return sys.stdin.readline().rstrip('\r\n')
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])

def solve():
	(n, m, k) = aj()
	C = aj()
	G = defaultdict(list)
	H = set()

	def addEdge(a, b):
		if (a, b) in H:
			return
		G[a].append(b)
		G[b].append(a)
		H.add((a, b))
		H.add((b, a))

	def dfs(node):
		d = deque()
		d.append(node)
		vis[node] = True
		c = Counter()
		while d:
			x = d.pop()
			c[C[x - 1]] += 1
			for i in G.get(x, []):
				if not vis[i]:
					vis[i] = True
					d.append(i)
		return c
	vis = [False] * (n + 1)
	s = set()
	for i in range(m):
		(u, v) = aj()
		addEdge(u, v)
		s.add(u)
		s.add(v)
	ans = 0
	for i in s:
		if not vis[i]:
			c = dfs(i)
			ans += sum(c.values())
			ans -= c.most_common(1)[0][1]
	print(ans)
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
solve()


from collections import Counter, defaultdict

class DSU:

	def __init__(self, n):
		self.parents = [i for i in range(n)]
		self.rank = [0 for i in range(n)]

	def find_parent(self, a):
		if a == self.parents[a]:
			return a
		else:
			b = self.find_parent(self.parents[a])
			self.parents[a] = b
			return b

	def join_sets(self, a, b):
		a = self.find_parent(a)
		b = self.find_parent(b)
		if a != b:
			if self.rank[a] < self.rank[b]:
				(a, b) = (b, a)
			self.parents[b] = a
			if self.rank[a] == self.rank[b]:
				self.rank[a] += 1
(n, m, k) = map(int, input().split(' '))
dsu = DSU(n)
colors = list(map(int, input().split(' ')))
for _ in range(m):
	(a, b) = map(int, input().split(' '))
	(a, b) = (a - 1, b - 1)
	dsu.join_sets(a, b)
cur_colors = defaultdict(Counter)
for i in range(n):
	cur_colors[dsu.find_parent(i)][colors[i]] += 1
ans = 0
for color_counter in cur_colors.values():
	ans += sum(color_counter.values()) - color_counter.most_common(1)[0][1]
print(ans)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
from bisect import bisect_left

def dfs(x):
	stack = [x]
	d = {}
	while stack:
		x = stack.pop()
		if x in visited:
			continue
		if c[x] in d:
			d[c[x]] += 1
		else:
			d[c[x]] = 1
		visited.add(x)
		for i in graph[x]:
			if i not in visited:
				stack.append(i)
	z = 0
	ma = 0
	for i in d:
		z += d[i]
		ma = max(ma, d[i])
	return z - ma
(n, m, k) = map(int, input().split())
c = list(map(int, input().split()))
graph = {i: set() for i in range(n)}
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a - 1].add(b - 1)
	graph[b - 1].add(a - 1)
count = 0
visited = set()
for i in range(n):
	if i not in visited:
		count += dfs(i)
print(count)


from collections import *
from sys import stdin

def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return list(stdin.readline()[:-1])

class graph:

	def __init__(self, gdict=None):
		if gdict is None:
			gdict = defaultdict(list)
		(self.gdict, self.edges, self.l) = (gdict, [], defaultdict(int))

	def get_vertices(self):
		return list(self.gdict.keys())

	def add_edge(self, node1, node2, w=None):
		self.gdict[node1].append(node2)
		self.gdict[node2].append(node1)
		self.l[node1] += 1
		self.l[node2] += 1

	def bfs_util(self, i):
		(queue, self.visit[i], color) = (deque([i]), 1, defaultdict(int, {c[i - 1]: 1}))
		while queue:
			s = queue.popleft()
			for i in self.gdict[s]:
				if self.visit[i] == 0:
					queue.append(i)
					self.visit[i] = 1
					color[c[i - 1]] += 1
		return sum(color.values()) - max(color.values())

	def bfs(self):
		(self.visit, self.cnt) = (defaultdict(int), 0)
		for i in self.get_vertices():
			if self.visit[i] == 0:
				self.cnt += self.bfs_util(i)
		return self.cnt
(n, m, k) = arr_inp(1)
(c, g) = (arr_inp(1), graph())
for i in range(m):
	(u, v) = arr_inp(1)
	g.add_edge(u, v)
print(g.bfs())


from collections import Counter
from sys import stdin
input = stdin.readline
(n, m, k) = map(int, input().split())
colors = [None] + [*map(int, input().split())]
soc = [[int(x) for x in input().split()] for i in range(m)]
allocated = set()
groups = dict()
cols = [None for i in range(n + 1)]
x = 1
for (i, j) in soc:
	if i in allocated and j in allocated:
		while type(groups[cols[i]]) == int:
			cols[i] = groups[cols[i]]
		while type(groups[cols[j]]) == int:
			cols[j] = groups[cols[j]]
		if cols[i] == cols[j]:
			pass
		else:
			groups[cols[i]].update(groups[cols[j]])
			groups[cols[j]] = cols[i]
	elif i in allocated:
		allocated.add(j)
		while type(groups[cols[i]]) == int:
			cols[i] = groups[cols[i]]
		groups[cols[i]][colors[j]] += 1
		cols[j] = cols[i]
	elif j in allocated:
		allocated.add(i)
		while type(groups[cols[j]]) == int:
			cols[j] = groups[cols[j]]
		groups[cols[j]][colors[i]] += 1
		cols[i] = cols[j]
	else:
		allocated.add(i)
		allocated.add(j)
		groups[x] = Counter([colors[i], colors[j]])
		cols[i] = x
		cols[j] = x
		x += 1
ans = 0
for i in groups:
	if type(groups[i]) == int:
		continue
	ans += sum(groups[i].values()) - groups[i].most_common(1)[0][1]
print(ans)