During the Steam Summer Sale, Jim's $N-1$ friends have purchased $\mbox{M}$ games, which are numbered from $\mbox{1}$ to $\mbox{M}$. The games are multiplayer. Jim has invited his friends to his basement where they will play by making a LAN-Party. 

Each friend has already decided the game he would like to play for the rest of the day. So there will be a group of friends who will play the same game together.

But then, they face a problem: Currently, none of the friends' PCs are connected. So they have to be connected using the available $\mbox{Q}$ wires. Jim decides to connect friends $u_i$ and $v_i$ with the $\boldsymbol{i}^{th}$ wire one by one. So he starts with wire 1, then with wire 2 and so on. 

A group can start playing their game, only if all the members are connected (if not directly, then there must exist a path connecting them). They want to start playing as soon as possible. 

For each game, find out the wire after adding which the group can start playing. It is also possible that a group will never get connected. In such a case, this group starts crying and you should display -1.

Input Format

On the first line there will be $N$, $\mbox{M}$ and $\mbox{Q}$ each separated by a single space. On the second line we will give you $N$ integers separated by a single space: The $\boldsymbol{i}$-th integer denotes the game friend $\boldsymbol{i}$ wants to play (all between $\mbox{1}$ and $\mbox{M}$). The next $\mbox{Q}$ lines will denote $\mbox{Q}$ wires: $i^{th}$ line denotes $i^{th}$ wire and is denoted by $u_i$ and $v_i$ pairs each separated by a single space. 

Constraints

$1\leq N,M\leq10^5$ For each game $\boldsymbol{i}$, the number of players playing $\boldsymbol{i}$ will be positive. 

$0\leq Q\leq10^5$  

Note
Each game is chosen by at least one player. If a group consists of only one member, then print 0, since this lucky (?) lone player can start right away!

Output Format

Print on the $\boldsymbol{i}^{th} $line the answer for the $\boldsymbol{i}^{th} $game. 

Sample Input
5 2 4
1 2 2 2 1
1 2 
2 3
1 5
4 5 

Sample Output
3
4

Explanation

The group with the game 1 can play after the 3^{rd} wire is added. The group with game 2 can play only after the 4^{th} wire has been added because after adding the 4^{th} wire, a path between (2,3) (3,4) and (2,4) gets created.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Starter code:

Solutions:
import sys

class Vertex(object):

	def __init__(self, i, c, cc):
		self.i = i
		self.c = c
		self.cc = cc
		self.e = []

def merge_cc(cc, v, i, j, res, n, color_counts):
	to_rem = j if len(cc[i][1]) > len(cc[j][1]) else i
	to_leave = j if to_rem == i else i
	cc[to_rem][2] = False
	for i in cc[to_rem][1]:
		v[i].cc = to_leave
		cc[to_leave][1].append(i)
		if v[i].c in cc[to_leave][0]:
			cc[to_leave][0][v[i].c] += 1
		else:
			cc[to_leave][0][v[i].c] = 1
		if cc[to_leave][0][v[i].c] == color_counts[v[i].c] and res[v[i].c] == -1:
			res[v[i].c] = n
	cc[to_rem][1] = []
(n, m, q) = (int(x) for x in input().strip().split(' '))
colors = [int(x) for x in input().strip().split(' ')]
vs = []
comps = {}
for i in range(n):
	vs.append(Vertex(i, colors[i], i))
	comps[i] = [{colors[i]: 1}, [i], True]
color_counts = {}
for c in colors:
	if c in color_counts:
		color_counts[c] += 1
	else:
		color_counts[c] = 1
res = dict(((c, -1) for c in set(colors)))
for i in color_counts:
	if color_counts[i] == 1:
		res[i] = 0
for i in range(q):
	(a, b) = (int(x) for x in input().strip().split(' '))
	a -= 1
	b -= 1
	vs[a].e.append(b)
	vs[b].e.append(a)
	if vs[a].cc != vs[b].cc:
		merge_cc(comps, vs, vs[a].cc, vs[b].cc, res, i + 1, color_counts)
for i in sorted(res.keys()):
	print(res[i])


from collections import defaultdict
NMQ = input().split()
N = int(NMQ[0])
M = int(NMQ[1])
Q = int(NMQ[2])
p_game = [0 for x in range(N)]
p_subgraph = [i for i in range(N)]
s_data = {}
s_members = {}
g_time = [-1 for x in range(M)]
g_count = [0 for x in range(M)]
games_read = input().split()
for p in range(N):
	g = int(games_read[p]) - 1
	p_game[p] = g
	i = p
	p_subgraph[p] = i
	s_data[i] = defaultdict(lambda : 0, {g: 1})
	s_members[i] = [p]
	g_count[g] += 1
for g in range(M):
	if g_count[g] == 1:
		g_time[g] = 0
t = 0
for q in range(Q):
	t += 1
	wire_read = input().split()
	p1 = int(wire_read[0]) - 1
	p2 = int(wire_read[1]) - 1
	s1 = p_subgraph[p1]
	s2 = p_subgraph[p2]
	if s1 == s2:
		continue
	for g in s_data[s2].keys():
		s_data[s1][g] += s_data[s2][g]
		if s_data[s1][g] == g_count[g] and g_time[g] == -1:
			g_time[g] = t
	s_data.pop(s2)
	for p in s_members[s2]:
		p_subgraph[p] = s1
	s_members[s1] += s_members.pop(s2)
for g_t in g_time:
	print(g_t)


import sys

class Vertex(object):

	def __init__(self, i, c, cc):
		self.i = i
		self.c = c
		self.cc = cc
		self.e = []

def merge_cc(cc, v, i, j, res, n, color_counts):
	to_rem = j if len(cc[i][1]) > len(cc[j][1]) else i
	to_leave = j if to_rem == i else i
	cc[to_rem][2] = False
	for i in cc[to_rem][1]:
		v[i].cc = to_leave
		cc[to_leave][1].append(i)
		if v[i].c in cc[to_leave][0]:
			cc[to_leave][0][v[i].c] += 1
		else:
			cc[to_leave][0][v[i].c] = 1
		if cc[to_leave][0][v[i].c] == color_counts[v[i].c] and res[v[i].c] == -1:
			res[v[i].c] = n
	cc[to_rem][1] = []
(n, m, q) = (int(x) for x in input().strip().split(' '))
colors = [int(x) for x in input().strip().split(' ')]
vs = []
comps = {}
for i in range(n):
	vs.append(Vertex(i, colors[i], i))
	comps[i] = [{colors[i]: 1}, [i], True]
color_counts = {}
for c in colors:
	if c in color_counts:
		color_counts[c] += 1
	else:
		color_counts[c] = 1
res = dict(((c, -1) for c in set(colors)))
for i in color_counts:
	if color_counts[i] == 1:
		res[i] = 0
for i in range(q):
	(a, b) = (int(x) for x in input().strip().split(' '))
	a -= 1
	b -= 1
	vs[a].e.append(b)
	vs[b].e.append(a)
	if vs[a].cc != vs[b].cc:
		merge_cc(comps, vs, vs[a].cc, vs[b].cc, res, i + 1, color_counts)
for i in sorted(res.keys()):
	print(res[i])


import sys

class Vertex(object):

	def __init__(self, i, c, cc):
		self.i = i
		self.c = c
		self.cc = cc
		self.e = []

def merge_cc(cc, v, i, j, res, n, color_counts):
	to_rem = j if len(cc[i][1]) > len(cc[j][1]) else i
	to_leave = j if to_rem == i else i
	cc[to_rem][2] = False
	for i in cc[to_rem][1]:
		v[i].cc = to_leave
		cc[to_leave][1].append(i)
		if v[i].c in cc[to_leave][0]:
			cc[to_leave][0][v[i].c] += 1
		else:
			cc[to_leave][0][v[i].c] = 1
		if cc[to_leave][0][v[i].c] == color_counts[v[i].c] and res[v[i].c] == -1:
			res[v[i].c] = n
	cc[to_rem][1] = []
(n, m, q) = (int(x) for x in input().strip().split(' '))
colors = [int(x) for x in input().strip().split(' ')]
vs = []
comps = {}
for i in range(n):
	vs.append(Vertex(i, colors[i], i))
	comps[i] = [{colors[i]: 1}, [i], True]
color_counts = {}
for c in colors:
	if c in color_counts:
		color_counts[c] += 1
	else:
		color_counts[c] = 1
res = dict(((c, -1) for c in set(colors)))
for i in color_counts:
	if color_counts[i] == 1:
		res[i] = 0
for i in range(q):
	(a, b) = (int(x) for x in input().strip().split(' '))
	a -= 1
	b -= 1
	vs[a].e.append(b)
	vs[b].e.append(a)
	if vs[a].cc != vs[b].cc:
		merge_cc(comps, vs, vs[a].cc, vs[b].cc, res, i + 1, color_counts)
for i in sorted(res.keys()):
	print(res[i])


import os
import sys

class Vertex(object):

	def __init__(self, i, c, cc):
		self.i = i
		self.c = c
		self.cc = cc
		self.e = []

def merge_cc(cc, v, i, j, res, n, color_counts):
	to_rem = j if len(cc[i][1]) > len(cc[j][1]) else i
	to_leave = j if to_rem == i else i
	cc[to_rem][2] = False
	for i in cc[to_rem][1]:
		v[i].cc = to_leave
		cc[to_leave][1].append(i)
		if v[i].c in cc[to_leave][0]:
			cc[to_leave][0][v[i].c] += 1
		else:
			cc[to_leave][0][v[i].c] = 1
		if cc[to_leave][0][v[i].c] == color_counts[v[i].c] and res[v[i].c] == -1:
			res[v[i].c] = n
	cc[to_rem][1] = []
(n, m, q) = (int(x) for x in input().strip().split(' '))
colors = [int(x) for x in input().strip().split(' ')]
vs = []
comps = {}
for i in range(n):
	vs.append(Vertex(i, colors[i], i))
	comps[i] = [{colors[i]: 1}, [i], True]
color_counts = {}
for c in colors:
	if c in color_counts:
		color_counts[c] += 1
	else:
		color_counts[c] = 1
res = dict(((c, -1) for c in set(colors)))
for i in color_counts:
	if color_counts[i] == 1:
		res[i] = 0
for i in range(q):
	(a, b) = (int(x) for x in input().strip().split(' '))
	a -= 1
	b -= 1
	vs[a].e.append(b)
	vs[b].e.append(a)
	if vs[a].cc != vs[b].cc:
		merge_cc(comps, vs, vs[a].cc, vs[b].cc, res, i + 1, color_counts)
for i in sorted(res.keys()):
	print(res[i])


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import math
import os
import random
import re
import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import math
import os
import random
import re
import sys
import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

class Vertex(object):

	def __init__(self, i, c, cc):
		self.i = i
		self.c = c
		self.cc = cc
		self.e = []

def merge_cc(cc, v, i, j, res, n, color_counts):
	to_rem = j if len(cc[i][1]) > len(cc[j][1]) else i
	to_leave = j if to_rem == i else i
	cc[to_rem][2] = False
	for i in cc[to_rem][1]:
		v[i].cc = to_leave
		cc[to_leave][1].append(i)
		if v[i].c in cc[to_leave][0]:
			cc[to_leave][0][v[i].c] += 1
		else:
			cc[to_leave][0][v[i].c] = 1
		if cc[to_leave][0][v[i].c] == color_counts[v[i].c] and res[v[i].c] == -1:
			res[v[i].c] = n
	cc[to_rem][1] = []
(n, m, q) = (int(x) for x in input().strip().split(' '))
colors = [int(x) for x in input().strip().split(' ')]
vs = []
comps = {}
for i in range(n):
	vs.append(Vertex(i, colors[i], i))
	comps[i] = [{colors[i]: 1}, [i], True]
color_counts = {}
for c in colors:
	if c in color_counts:
		color_counts[c] += 1
	else:
		color_counts[c] = 1
res = dict(((c, -1) for c in set(colors)))
for i in color_counts:
	if color_counts[i] == 1:
		res[i] = 0
for i in range(q):
	(a, b) = (int(x) for x in input().strip().split(' '))
	a -= 1
	b -= 1
	vs[a].e.append(b)
	vs[b].e.append(a)
	if vs[a].cc != vs[b].cc:
		merge_cc(comps, vs, vs[a].cc, vs[b].cc, res, i + 1, color_counts)
for i in sorted(res.keys()):
	print(res[i])


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import math
import os
import random
import re
import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)


import sys

def read():
	l = sys.stdin.readline()
	if l[-1] == '\n':
		l = l[:-1]
	xs = filter(lambda x: len(x) > 0, l.split(' '))
	return map(int, xs)
(n, m, q) = read()
ps = list(map(lambda x: x - 1, read()))
gs = [set() for ix in range(m)]
for ix in range(len(ps)):
	gs[ps[ix]].add(ix)
uf = []
for ix in range(len(ps)):
	uf.append([ix, 0, set([ps[ix]])])
res = []
for ix in range(len(gs)):
	if len(gs[ix]) < 2:
		res.append(0)
	else:
		res.append(-1)

def find(x):
	if uf[x][0] == x:
		return x
	r = find(uf[x][0])
	uf[x][0] = r
	return r

def union(u, v, ix):
	ur = find(u)
	vr = find(v)
	(ur, uh, us) = uf[ur]
	(vr, vh, vs) = uf[vr]
	if uh > vh:
		uf[vr][0] = ur
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	elif vh > uh:
		uf[ur][0] = vr
		uf[vr][2] |= us
		for g in vs:
			gs[g].discard(ur)
			gs[g].add(vr)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
	else:
		uf[vr][0] = ur
		uf[ur][1] += 1
		uf[ur][2] |= vs
		for g in vs:
			gs[g].discard(vr)
			gs[g].add(ur)
			if res[g] < 0 and len(gs[g]) == 1:
				res[g] = ix + 1
for ix in range(q):
	(u, v) = map(lambda x: x - 1, read())
	union(u, v, ix)
for r in res:
	print(r)