Read problems statements in Mandarin Chinese  and Russian. 

This summer, there is a worldwide competition being held in Chef Town and some of the best chefs of the world are participating. The rules of this competition are quite simple. 

Each participant needs to bring his or her best dish. The judges will initially assign a score to each of the dishes. Now, several rounds will follow. In each round, any two chefs will be called up on the stage. Each of the chefs can then choose any one dish to battle against the other chef and the one having the dish with the higher score will win this round. The winner of the round will also obtain all the dishes of the loser who will then be eliminated. In case both the dishes have equal scores, this round will be considered as a tie and nothing else will happen. Note that initially each chef will have only one dish and all the chefs play the rounds optimally. 

Your task is to simulate and answer some queries related to this. You will be given N dishes numbered from 1 to N with the i^{th} dish belonging to the i^{th} chef initially. You will also be given an array S where S[i] denotes the score given by the judges to the i^{th} dish before starting the rounds. You will have to answer Q queries, each of which can be of the following types : 

1.  0 x y : This denotes that the chef containing dish number x  competes with the chef containing dish number  y  currently in this round. If a single chef is the owner of both the dishes, print "Invalid query!" (without quotes), otherwise execute and store the result of this round as described by the rules above. 

2.  1 x  : You need to output the index of the chef containing dish x  at this point.

------ Input ------ 

First line of input contains an integer T denoting the number of test cases. For each test case, the first line contains an integer N denoting the number of chefs in the contest. The next line contains N space separated integers where the i^{th} integer represents S[i]. The next line contains an integer Q denoting the number of queries.  Q  lines follow where each line can be of the format  0 x y  or  1 x  as described in the problem statement. 

------ Output ------ 

For each test, print in each line the answer for the queries as described in the problem statement .

------ Constraints ------ 

$ 1 ≤ T ≤ 25 $
$ 1 ≤ N ≤ 10000(10^{4}) $
$ 0 ≤ S[i] ≤ 1000000(10^{6}) 
$$ 1 ≤ Q ≤ 10000(10^{4}) 
$$ 1 ≤ x, y ≤  N 

----- Sample Input 1 ------ 
1
2
1 2
2
0 1 2
1 1
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 

There are two chefs with scores of dishes  1  and  2  respectively. After the first query, chef  2  acquires dish  1  since  S[2] > S[1] . Hence, the answer for the second query, i.e owner of the first dish is chef 2.

Difficulty: MEDIUM_HARD
Tags: Spanning trees

Data structures
Skill types: Data structures

Starter code:

Solutions:
def find(child):
	new_parent = child
	while new_parent != parents[new_parent]:
		new_parent = parents[new_parent]
	while child != parents[child]:
		temp = parents[child]
		parents[child] = new_parent
		child = temp
	return new_parent

def union(root1, root2):
	(real_root1, real_root2) = (find(root1), find(root2))
	if ratings[real_root1] > ratings[real_root2]:
		parents[real_root2] = real_root1
	elif ratings[real_root1] < ratings[real_root2]:
		parents[real_root1] = real_root2
for _ in range(int(input().strip())):
	n = int(input().strip())
	parents = list(range(n))
	ratings = list(map(int, input().strip().split()))
	queries = int(input())
	for query in range(queries):
		inp = list(map(int, input().strip().split()))
		if inp[0] == 0:
			(root1, root2) = (inp[1] - 1, inp[2] - 1)
			if find(root1) == find(root2):
				print('Invalid query!')
			else:
				union(root1, root2)
		else:
			print(find(inp[1] - 1) + 1)


import sys
from sys import stdin
sys.setrecursionlimit(10 ** 6)

def find(n):
	if grupy[n] == n:
		return n
	grupy[n] = find(grupy[n])
	return grupy[n]

def union(l1, l2):
	s1 = find(l1)
	s2 = find(l2)
	if punkty[s1] > punkty[s2]:
		wygrany = s1
		przegrany = s2
	elif punkty[s2] > punkty[s1]:
		wygrany = s2
		przegrany = s1
	elif punkty[s2] == punkty[s1] and s1 != s2:
		return
	if s1 != s2:
		grupy[przegrany] = wygrany
		punkty[przegrany] = 0
	else:
		print('Invalid query!')
il_t = int(stdin.readline())
for i in range(il_t):
	il_dan = int(stdin.readline())
	grupy = list(range(0, il_dan + 1))
	punkty = [0] + [int(x) for x in stdin.readline().split()]
	il_pyt = int(stdin.readline())
	for i in range(il_pyt):
		pytanie = [int(x) for x in stdin.readline().split()]
		if pytanie[0] == 0:
			union(pytanie[1], pytanie[2])
		else:
			print(find(pytanie[1]))


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():

	def find(a):
		x = []
		while par[a] != a:
			x.append(a)
			a = par[a]
		for i in x:
			par[i] = a
		return a

	def union(x, y):
		x = find(x)
		y = find(y)
		if l[x] > l[y]:
			par[y] = x
		elif l[x] < l[y]:
			par[x] = y
	n = inp()
	l = [0] + li()
	par = {i: i for i in range(n + 1)}
	q = inp()
	for i in range(q):
		p = li()
		if len(p) == 3:
			(a, b) = p[1:]
			(x, y) = (find(a), find(b))
			if x == y:
				pr('Invalid query!')
			else:
				union(x, y)
		else:
			pr(find(p[1]))
for _ in range(inp()):
	solve()


class Subset:

	def __init__(self, parent, rank, score, owner):
		self.parent = parent
		self.rank = rank
		self.score = score
		self.owner = owner

def find(subsets, node):
	if subsets[node].parent != node:
		subsets[node].parent = find(subsets, subsets[node].parent)
	return subsets[node].parent

def union(subsets, u, v):
	if subsets[u].score == subsets[v].score:
		return
	if subsets[u].rank > subsets[v].rank:
		subsets[v].parent = u
		if subsets[u].score < subsets[v].score:
			subsets[u].score = subsets[v].score
			subsets[u].owner = subsets[v].owner
	elif subsets[v].rank > subsets[u].rank:
		subsets[u].parent = v
		if subsets[v].score < subsets[u].score:
			subsets[v].score = subsets[u].score
			subsets[v].owner = subsets[u].owner
	else:
		subsets[v].parent = u
		subsets[u].rank += 1
		if subsets[u].score < subsets[v].score:
			subsets[u].score = subsets[v].score
			subsets[u].owner = subsets[v].owner
t = int(input())
while t != 0:
	n = int(input())
	s = list(map(int, input().split()))
	subsets = []
	subsets.append(Subset(0, 0, 0, 0))
	for i in range(1, n + 1):
		subsets.append(Subset(i, 0, s[i - 1], i))
	q = int(input())
	while q != 0:
		x = list(map(int, input().split()))
		if x[0] == 0:
			u_id = find(subsets, x[1])
			v_id = find(subsets, x[2])
			if u_id == v_id:
				print('Invalid query!')
			else:
				union(subsets, u_id, v_id)
		else:
			u_id = find(subsets, x[1])
			print(subsets[u_id].owner)
		q -= 1
	t -= 1


import sys

def find(i):
	li = []
	while i != dic[i]:
		dic[i] = dic[dic[i]]
		i = dic[i]
	return i

def union(a, b):
	if arr[a] > arr[b]:
		dic[b] = a
	elif arr[b] > arr[a]:
		dic[a] = b
t = int(input())
while t:
	t -= 1
	n = int(input())
	ar = list(map(int, sys.stdin.readline().strip().split()))
	arr = [0] + ar
	dic = {k: k for k in range(n + 1)}
	q = int(input())
	while q:
		q -= 1
		lis = list(map(int, sys.stdin.readline().strip().split()))
		if lis[0] == 0:
			(x, y) = (find(lis[1]), find(lis[2]))
			if x == y:
				print('Invalid query!')
			else:
				union(x, y)
		else:
			print(find(lis[1]))


import sys
sys.setrecursionlimit(100000)

def find(x):
	if x != l[x]:
		l[x] = find(l[x])
	return l[x]

def union(x, y):
	x1 = find(x)
	y1 = find(y)
	if x1 == y1:
		print('Invalid query!')
	elif s[x1] > s[y1]:
		l[y1] = x1
	elif s[y1] > s[x1]:
		l[x1] = y1
for t in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	s = [0] + s
	l = [i for i in range(n + 2)]
	for _ in range(int(input())):
		q = list(map(int, input().split()))
		if len(q) == 3 and q[0] == 0:
			(x, y) = (q[1], q[2])
			union(x, y)
		else:
			x = q[1]
			u = find(x)
			print(u)


x = int(input())
dish = []
owner = []

def calculate(a, b):
	f1 = root(a)
	f2 = root(b)
	if f1 == f2:
		print('Invalid query!')
	elif dish[f1] > dish[f2]:
		owner[f2] = owner[f1]
	elif dish[f1] < dish[f2]:
		owner[f1] = owner[f2]

def root(i):
	while owner[i] != i:
		owner[i] = owner[owner[i]]
		i = owner[i]
	return i
while x > 0:
	n = int(input())
	dish = list(map(int, input().split()))
	for i in range(n):
		owner.append(i)
	q = int(input())
	query = []
	for s in range(0, q):
		query = list(map(int, input().split()))
		if query[0] == 0:
			calculate(query[1] - 1, query[2] - 1)
		else:
			ow = root(query[1] - 1)
			print(ow + 1)
		query.clear()
	dish.clear()
	owner.clear()
	x -= 1


from sys import setrecursionlimit
setrecursionlimit(int(1000000.0))

class DSU:

	def __init__(self, s):
		self.p = [-(i + 1) for i in s]

	def find(self, n):
		if self.p[n] < 0:
			return n
		self.p[n] = self.find(self.p[n])
		return self.p[n]

	def union(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			print('Invalid query!')
		elif self.p[a] == self.p[b]:
			return
		elif self.p[a] < self.p[b]:
			self.p[a] = min(self.p[a], self.p[b])
			self.p[b] = a
		else:
			self.p[b] = min(self.p[a], self.p[b])
			self.p[a] = b
t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	d = DSU(s)
	q = int(input())
	for i in range(q):
		a = list(map(int, input().split()))
		if a[0] == 0:
			d.union(a[1] - 1, a[2] - 1)
		else:
			print(d.find(a[1] - 1) + 1)


def find(child):
	new_parent = child
	while new_parent != parents[new_parent]:
		new_parent = parents[new_parent]
	while child != parents[child]:
		temp = parents[child]
		parents[child] = new_parent
		child = temp
	return new_parent

def union(r1, r2):
	(mr1, mr2) = (find(r1), find(r2))
	if ratings[chef[mr1]] > ratings[chef[mr2]]:
		parents[mr2] = mr1
		chef[mr2] = chef[mr1]
	elif ratings[chef[mr1]] < ratings[chef[mr2]]:
		parents[mr1] = mr2
		chef[mr1] = chef[mr2]
for _ in range(int(input())):
	n = int(input())
	parents = list(range(n))
	chef = list(range(n))
	ratings = list(map(int, input().strip().split()))
	queries = int(input())
	for query in range(queries):
		inp = list(map(int, input().strip().split()))
		if inp[0] == 0:
			(r1, r2) = (inp[1] - 1, inp[2] - 1)
			if find(r1) == find(r2):
				print('Invalid query!')
			else:
				union(r1, r2)
		else:
			print(find(inp[1] - 1) + 1)


def root(i):
	while index[i] != i:
		index[i] = index[index[i]]
		i = index[i]
	return i

def union(a, b):
	if arr[a] > arr[b]:
		index[b] = a
	elif arr[b] > arr[a]:
		index[a] = b
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	arr = [0] + ar
	index = [i for i in range(n + 1)]
	for t in range(int(input())):
		compete = list(map(int, input().split()))
		if compete[0] == 0:
			(x, y) = (root(compete[1]), root(compete[2]))
			if x == y:
				print('Invalid query!')
			else:
				union(x, y)
		else:
			print(root(compete[1]))


def root(i):
	while index[i] != i:
		index[i] = index[index[i]]
		i = index[i]
	return i

def union(a, b):
	if arr[a] > arr[b]:
		index[b] = a
	elif arr[b] > arr[a]:
		index[a] = b
for _ in range(int(input())):
	n1 = int(input())
	ar = list(map(int, input().split()))
	arr = [0] + ar
	index = [i for i in range(n1 + 1)]
	for t1 in range(int(input())):
		compete = list(map(int, input().split()))
		if compete[0] == 0:
			(x1, y1) = (root(compete[1]), root(compete[2]))
			if x1 == y1:
				print('Invalid query!')
			else:
				union(x1, y1)
		else:
			print(root(compete[1]))


class DisjointSets:

	def __init__(self, size):
		self.scores = []
		self.size = size
		self.dish_chef = [i for i in range(size + 1)]

	def find_chef(self, dish_num):
		while self.dish_chef[dish_num] != dish_num:
			self.dish_chef[dish_num] = self.dish_chef[self.dish_chef[dish_num]]
			dish_num = self.dish_chef[dish_num]
		return dish_num

	def modify_chefs(self, dish1, dish2):
		chef1 = self.find_chef(dish1)
		chef2 = self.find_chef(dish2)
		if chef1 == chef2:
			print('Invalid query!')
			return
		if self.scores[chef1] > self.scores[chef2]:
			self.dish_chef[chef2] = chef1
		elif self.scores[chef1] < self.scores[chef2]:
			self.dish_chef[chef1] = chef2

	def input_scores(self):
		self.scores = list(map(int, input().split()))
		self.scores.insert(0, 0)
T = int(input())
for i in range(T):
	N = int(input())
	dis_set = DisjointSets(N)
	dis_set.input_scores()
	num_queries = int(input())
	for j in range(num_queries):
		list_ = input().split()
		if list_[0] == '0':
			dis_set.modify_chefs(int(list_[1]), int(list_[2]))
		else:
			print(dis_set.find_chef(int(list_[1])))


from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

def findParent(dish, parent):
	if parent[dish] == dish:
		return dish
	else:
		parent[dish] = findParent(parent[dish], parent)
		return parent[dish]
for t in range(int(input())):
	n = int(input())
	S = list(map(int, input().split()))
	parent = [i for i in range(n)]
	chef = [score for score in S]
	for _ in range(int(input())):
		query = list(map(int, input().strip().split()))
		if query[0] == 0:
			(x, y) = (query[1], query[2])
			x -= 1
			y -= 1
			(dish1, dish2) = (x, y)
			chef1 = findParent(dish1, parent)
			chef2 = findParent(dish2, parent)
			if chef1 == chef2:
				print('Invalid query!')
			elif chef[chef1] > chef[chef2]:
				parent[chef2] = chef1
			elif chef[chef1] < chef[chef2]:
				parent[chef1] = chef2
		else:
			x = int(query[1])
			print(findParent(x - 1, parent) + 1)


def find_parent(x):
	y = x
	while y != parent[y]:
		y = parent[y]
	while x != parent[x]:
		z = parent[x]
		parent[x] = y
		x = z
	return y
for _ in range(int(input())):
	N = int(input())
	S = [int(x) for x in input().split()]
	parent = [i for i in range(N)]
	chef = [i for i in range(N)]
	for _ in range(int(input())):
		query = [int(x) for x in input().split()]
		if query[0] == 0:
			x = find_parent(query[1] - 1)
			y = find_parent(query[2] - 1)
			if x == y:
				print('Invalid query!')
			elif S[chef[x]] > S[chef[y]]:
				parent[y] = x
				chef[y] = chef[x]
			elif S[chef[x]] < S[chef[y]]:
				parent[x] = y
				chef[x] = chef[y]
		else:
			print(chef[find_parent(query[1] - 1)] + 1)


T = int(input())
for tc in range(T):
	N = int(input())
	Z = list(map(int, input().split()))
	S = [0] + Z
	Q = int(input())
	chef = [i for i in range(N + 1)]
	for i in range(Q):
		order = list(map(int, input().split()))
		if order[0] == 0:
			while chef[order[1]] != order[1]:
				chef[order[1]] = chef[chef[order[1]]]
				order[1] = chef[order[1]]
			while chef[order[2]] != order[2]:
				chef[order[2]] = chef[chef[order[2]]]
				order[2] = chef[order[2]]
			if order[1] == order[2]:
				print('Invalid query!')
			elif S[order[1]] > S[order[2]]:
				chef[order[2]] = order[1]
			elif S[order[1]] < S[order[2]]:
				chef[order[1]] = order[2]
		else:
			while chef[order[1]] != order[1]:
				chef[order[1]] = chef[chef[order[1]]]
				order[1] = chef[order[1]]
			print(order[1])


def findparent(x):
	originalx = x
	while x != -1:
		oldx = x
		x = parents[x]
	if originalx != oldx:
		parents[originalx] = oldx
	return oldx
for _ in range(int(input())):
	n = int(input())
	parents = [-1 for i in range(n)]
	s = list(map(int, input().split()))
	q = int(input())
	for i in range(q):
		qr = list(map(int, input().split()))
		if qr[0] == 1:
			print(findparent(qr[1] - 1) + 1)
		else:
			p1 = findparent(qr[1] - 1)
			p2 = findparent(qr[2] - 1)
			if p1 == p2:
				print('Invalid query!')
			elif s[p1] < s[p2]:
				parents[p1] = p2
			elif s[p2] < s[p1]:
				parents[p2] = p1


lostTo = [-1] * 10000

def findOwner(i):
	path = [i]
	while lostTo[i] >= 0:
		i = lostTo[i]
		path.append(i)
	for j in range(len(path) - 1):
		lostTo[path[j]] = i
	return i
for _ in range(int(input())):
	N = int(input())
	for i in range(N):
		lostTo[i] = -1
	S = list(map(int, input().split()))
	bestDish = []
	for i in range(N):
		bestDish.append(S[i])
	for _ in range(int(input())):
		q = list(map(int, input().split()))
		if q[0] == 1:
			print(findOwner(q[1] - 1) + 1)
		else:
			o1 = findOwner(q[1] - 1)
			o2 = findOwner(q[2] - 1)
			if o1 == o2:
				print('Invalid query!')
			else:
				if bestDish[o1] > bestDish[o2]:
					lostTo[o2] = o1
				if bestDish[o1] < bestDish[o2]:
					lostTo[o1] = o2


class union:

	def __init__(self, n):
		self.n = n
		self.array = [i for i in range(n)]
		self.size = n * [1]
		self.value = n * [0]

	def root_of(self, pos):
		if pos >= self.n or pos < 0:
			return -1
		link_to_root = []
		p = pos
		while self.array[p] != p:
			link_to_root.append(p)
			p = self.array[p]
		root = p
		for p in link_to_root:
			self.array[p] = root
		return root

	def connect(self, x, y):
		root_x = self.root_of(x)
		root_y = self.root_of(y)
		if root_x == root_y:
			return False
		if self.value[root_x] > self.value[root_y]:
			self.array[root_y] = root_x
		elif self.value[root_x] < self.value[root_y]:
			self.array[root_x] = root_y
		return True

	def count_of_trees(self):
		total = 0
		for i in range(self.n):
			if self.array[i] == i:
				total += 1
		return total

	def trees_values(self):
		values = []
		for i in range(self.n):
			if self.array[i] == i:
				values.append(self.value[i])
		return values

	def __str__(self):
		s = ''
		for el in self.array:
			s += str(el) + ' '
		return s
for _ in range(int(input().strip())):
	n = int(input().strip())
	un = union(n)
	v = list(map(int, input().strip().split()))
	for i in range(n):
		un.value[i] = v[i]
	for _ in range(int(input().strip())):
		ar = list(map(int, input().strip().split()))
		if ar[0] == 0:
			done = un.connect(ar[1] - 1, ar[2] - 1)
			if not done:
				print('Invalid query!')
		else:
			print(un.root_of(ar[1] - 1) + 1)


import sys
sys.setrecursionlimit(10 ** 4)

def union(parent, p, q, rank):
	a = find(parent, p)
	b = find(parent, q)
	parent[b] = a

def find(parent, x):
	if parent[x] != x:
		parent[x] = find(parent, parent[x])
	return parent[x]
t = int(input())
for i in range(t):
	n = int(input())
	rank = [0] * (n + 1)
	parent = [i for i in range(n + 1)]
	s = [0] + [int(i) for i in input().split()]
	q = int(input())
	for i in range(q):
		a = list(map(int, input().split()))
		if a[0] == 0:
			p = find(parent, a[1])
			q = find(parent, a[2])
			if p == q:
				print('Invalid query!')
			elif s[p] > s[q]:
				union(parent, p, q, rank)
			elif s[p] < s[q]:
				union(parent, q, p, rank)
		else:
			print(find(parent, a[1]))


from sys import stdin, stdout, setrecursionlimit
import math
import bisect
import resource
resource.setrlimit(resource.RLIMIT_STACK, (2 ** 29, -1))
setrecursionlimit(10 ** 6)

class DSU:

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

	def find_set(self, v):
		if v == self.parent[v]:
			return v
		self.parent[v] = self.find_set(self.parent[v])
		return self.parent[v]

	def union(self, a, b):
		a = self.find_set(a)
		b = self.find_set(b)
		if a != b:
			if cost[a] < cost[b]:
				self.parent[a] = b
			elif cost[a] > cost[b]:
				self.parent[b] = a
			return False
		else:
			return True

def main():
	try:
		for _ in range(I()):
			n = I()
			global cost
			cost = [0] + list(In())
			nq = I()
			dsu = DSU(n)
			for q in range(nq):
				l = list(In())
				if l[0] == 1:
					z = dsu.find_set(l[1])
					print(z)
				else:
					ok = dsu.union(l[1], l[2])
					if ok:
						print('Invalid query!')
	except:
		pass

def add(a, b, c):
	res = a + b
	if res >= c:
		return res - c
	else:
		return res

def mod(a, b, c):
	res = a * b
	if res >= c:
		return res % c
	else:
		return res

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	w = a // gcd(a, b)
	return w * b

def expo(a, b):
	(x, y) = (1, a)
	while b > 0:
		if b & 1:
			x = x * y
		y = y * y
		b >>= 1
	return x

def power(a, b, m):
	(x, y) = (1,)
	while b > 0:
		if b & 1:
			x = mod(x, y, m)
		y = mod(y, y, m)
		b >>= 1
	return x

def L():
	return list(map(int, stdin.readline().split()))

def In():
	return map(int, stdin.readline().split())

def I():
	return int(stdin.readline())
P = 1000000007
main()


import sys
sys.setrecursionlimit(10000)

class DisjointSet:

	def __init__(self, n):
		p = [0] * (n + 1)
		for i in range(1, n + 1):
			p[i] = i
		self.p = p
		self.n = n

	def find(self, x):
		if self.p[x] != x:
			self.p[x] = self.find(self.p[x])
			return self.p[x]
		return self.p[x]

	def union(self, dishscore, pa, pb):
		if pa != pb:
			if dishscore[pa - 1] > dishscore[pb - 1]:
				self.p[pb] = pa
			elif dishscore[pb - 1] > dishscore[pa - 1]:
				self.p[pa] = pb
		else:
			sys.stdout.write('Invalid query!\n')

def dishown():
	t = int(sys.stdin.readline())
	while t > 0:
		n = int(sys.stdin.readline())
		disset = DisjointSet(n)
		dishscore = list(map(int, sys.stdin.readline().split()))
		q = int(sys.stdin.readline())
		for i in range(q):
			query = list(map(int, sys.stdin.readline().split()))
			if query[0] == 0:
				a = query[1]
				b = query[2]
				pa = disset.find(a)
				pb = disset.find(b)
				disset.union(dishscore, pa, pb)
			else:
				sys.stdout.write(str(disset.find(query[1])) + '\n')
		t -= 1
dishown()


def find(a):
	parr = a
	while par[parr] != parr:
		parr = par[parr]
	while par[a] != a:
		temp = par[a]
		par[a] = parr
		a = temp
	return parr

def union(a, b):
	(a, b) = (find(a), find(b))
	if a == b:
		return
	par[b] = a
ts = int(input())
while ts > 0:
	n = int(input())
	cost = list(map(int, input().split()))
	par = [i for i in range(n + 1)]
	q = int(input())
	for jj in range(q):
		query = list(map(int, input().split()))
		(a, b, x) = (0, 0, 0)
		if query[0] == 0:
			a = query[1]
			b = query[2]
			para = find(a)
			parb = find(b)
			if para == parb:
				print('Invalid query!')
			if cost[para - 1] > cost[parb - 1]:
				union(para, parb)
			elif cost[para - 1] < cost[parb - 1]:
				union(parb, para)
		else:
			x = query[1]
			print(find(x))
	ts -= 1


def union(i, j):
	fi = find(i)
	fj = find(j)
	if best[fi] > best[fj]:
		dsu[fj] = fi
	elif best[fj] > best[fi]:
		dsu[fi] = fj

def find(x):
	while dsu[x] != x:
		dsu[x] = dsu[dsu[x]]
		x = dsu[x]
		best[x] = max(best[x], best[dsu[x]])
		best[dsu[x]] = max(best[x], best[dsu[x]])
	return x
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	dsu = [i for i in range(n)]
	best = [a[i] for i in range(n)]
	for i in range(q):
		quer = list(map(int, input().split()))
		if quer[0] == 1:
			print(find(quer[1] - 1) + 1)
		else:
			u1 = find(quer[1] - 1)
			u2 = find(quer[2] - 1)
			if u1 == u2:
				print('Invalid query!')
			else:
				union(quer[2] - 1, quer[1] - 1)


def find1(owner, x):
	z = x
	while owner[x] != -1:
		x = owner[x]
	while owner[z] != -1:
		temp = owner[z]
		owner[z] = x
		z = temp
	return x
t = int(input())
for ijk in range(0, t):
	n = int(input())
	s = list(map(int, input().strip().split()))
	q = int(input())
	owner = [-1] * n
	for i in range(0, q):
		query = list(map(int, input().strip().split()))
		if query[0] == 0:
			if find1(owner, query[1] - 1) == find1(owner, query[2] - 1):
				print('Invalid query!')
			else:
				x1 = find1(owner, query[1] - 1)
				x2 = find1(owner, query[2] - 1)
				if s[x1] > s[x2]:
					owner[x2] = x1
				elif s[x2] > s[x1]:
					owner[x1] = x2
		else:
			ans = find1(owner, query[1] - 1)
			print(ans + 1)


def find_parent(x):
	y = x
	while y != parent[y]:
		y = parent[y]
	while x != parent[x]:
		z = parent[x]
		parent[x] = y
		x = z
	return y
T = int(input())
for i in range(0, T):
	N = int(input())
	S = [*map(int, input().split())]
	parent = [i for i in range(0, N)]
	chef = [i for i in range(0, N)]
	Q = int(input())
	for j in range(0, Q):
		query = [*map(int, input().split())]
		if query[0] == 0:
			x = find_parent(query[1] - 1)
			y = find_parent(query[2] - 1)
			if x == y:
				print('Invalid query!')
			elif S[chef[x]] > S[chef[y]]:
				parent[y] = x
				chef[y] = chef[x]
			elif S[chef[x]] < S[chef[y]]:
				parent[x] = y
				chef[x] = chef[y]
		else:
			print(chef[find_parent(query[1] - 1)] + 1)


import sys
sys.setrecursionlimit(10000)

class Node:

	def __init__(self, data, score):
		self.data = data
		self.score = score
		self.parent = self
		self.rank = 1

def find_root(node):
	if node != node.parent:
		node.parent = find_root(node.parent)
		return node.parent
	return node.parent

def union_nodes(node_1, node_2):
	(root_1, root_2) = (find_root(node_1), find_root(node_2))
	if root_1 == root_2:
		return '-1'
	elif root_1.score > root_2.score:
		root_2.parent = root_1
	elif root_1.score < root_2.score:
		root_1.parent = root_2
t = int(sys.stdin.readline())
for _ in range(t):
	N = int(sys.stdin.readline())
	Scores = list(map(int, sys.stdin.readline().strip().split(' ')))
	vertex = [Node(i, s) for (i, s) in zip(range(1, N + 1), Scores)]
	Q = int(sys.stdin.readline())
	for i in range(Q):
		query = list(map(int, sys.stdin.readline().strip().split(' ')))
		if query[0] == 0:
			(x, y) = (query[1], query[2])
			result = union_nodes(vertex[x - 1], vertex[y - 1])
			if result == '-1':
				print('Invalid query!')
		elif query[0] == 1:
			x = query[1]
			chef = find_root(vertex[x - 1])
			print(chef.data)