You have an array of integers (initially empty).

You have to perform $q$ queries. Each query is of one of two types:

"$1$ $x$" — add the element $x$ to the end of the array;

"$2$ $x$ $y$" — replace all occurrences of $x$ in the array with $y$.

Find the resulting array after performing all the queries.


-----Input-----

The first line contains a single integer $q$ ($1 \le q \le 5 \cdot 10^5$) — the number of queries.

Next $q$ lines contain queries (one per line). Each query is of one of two types:

"$1$ $x$" ($1 \le x \le 5 \cdot 10^5$);

"$2$ $x$ $y$" ($1 \le x, y \le 5 \cdot 10^5$).

It's guaranteed that there is at least one query of the first type.


-----Output-----

In a single line, print $k$ integers — the resulting array after performing all the queries, where $k$ is the number of queries of the first type.


-----Examples-----

Input
7
1 3
1 1
2 1 2
1 2
1 1
1 2
2 1 3
Output
3 2 2 3 2
Input
4
1 1
1 2
1 1
2 2 2
Output
1 2 1
Input
8
2 1 4
1 1
1 4
1 2
2 2 4
2 4 3
1 2
2 2 7
Output
1 3 3 7


-----Note-----

In the first example, the array changes as follows:

$[]$ $\rightarrow$ $[3]$ $\rightarrow$ $[3, 1]$ $\rightarrow$ $[3, 2]$ $\rightarrow$ $[3, 2, 2]$ $\rightarrow$ $[3, 2, 2, 1]$ $\rightarrow$ $[3, 2, 2, 1, 2]$ $\rightarrow$ $[3, 2, 2, 3, 2]$.

In the second example, the array changes as follows:

$[]$ $\rightarrow$ $[1]$ $\rightarrow$ $[1, 2]$ $\rightarrow$ $[1, 2, 1]$ $\rightarrow$ $[1, 2, 1]$.

In the third example, the array changes as follows:

$[]$ $\rightarrow$ $[]$ $\rightarrow$ $[1]$ $\rightarrow$ $[1, 4]$ $\rightarrow$ $[1, 4, 2]$ $\rightarrow$ $[1, 4, 4]$ $\rightarrow$ $[1, 3, 3]$ $\rightarrow$ $[1, 3, 3, 2]$ $\rightarrow$ $[1, 3, 3, 7]$.

Source: codeforces | Difficulty: HARD
Tags: Spanning trees

Data structures

Implementation

Constructive algorithms


Solutions:
from sys import *
input = stdin.readline
q = int(input())
r = list(range(500005))
g = []
ans = []
for i in range(q):
	qr = list(map(int, input().split()))
	g.append(qr)
for x in g[::-1]:
	if x[0] == 1:
		ans.append(str(r[x[1]]))
	else:
		r[x[1]] = r[x[2]]
print(*ans[::-1])


from collections import defaultdict
n = int(input())
d = defaultdict(list)
a = []
mp = [i for i in range(0, 500001)]
for i in range(n):
	A = list(map(int, input().split()))
	if A[0] == 1:
		a.append((A[0], A[1]))
	else:
		a.append((A[0], A[1], A[2]))
ans = []
for i in range(n - 1, -1, -1):
	if len(a[i]) == 2:
		ans.append(mp[a[i][1]])
	else:
		mp[a[i][1]] = mp[a[i][2]]
ans = ans[::-1]
print(*ans)


q = int(input())
l = []
m = []
d = {}
for _ in range(q):
	a = input().split()
	l.append(a)
for x in l[::-1]:
	if x[0] == '1':
		if x[1] in d:
			m.append(d[x[1]])
		else:
			m.append(x[1])
	elif x[2] in d:
		d[x[1]] = d[x[2]]
	else:
		d[x[1]] = x[2]
m = m[::-1]
print(*m)


def solver():
	n = int(input())
	final = []
	writer = []
	changer = {}
	for i in range(n):
		writer.append(list(map(int, input().split())))
	for i in reversed(writer):
		if i[0] == 1:
			if i[1] not in changer:
				dummy = i[1]
			else:
				dummy = changer[i[1]]
			final.append(dummy)
		elif i[2] not in changer:
			changer[i[1]] = i[2]
		else:
			changer[i[1]] = changer[i[2]]
	print(*final[::-1])
solver()


import sys
from math import factorial, gcd
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest, nsmallest
from itertools import groupby, accumulate
from copy import deepcopy
MOD = 10 ** 9 + 7
INF = float('inf')
input = sys.stdin.readline
rl = lambda : list(map(int, input().split()))
rs = lambda : sys.stdin.readline().strip()
n = 0
arr = []
change = []
for _ in range(int(input())):
	q = rs().split()
	if q[0] == '1':
		arr.append(q[-1])
		n += 1
	else:
		(x, y) = q[1:]
		if x == y or n == 0:
			continue
		change.append((x, y, n - 1))
if change:
	(x, y, idx) = change[-1]
	D = {x: y}
	j = len(change) - 2
	for i in range(n - 1, -1, -1):
		if i > idx:
			continue
		while j >= 0 and change[j][-1] == i:
			(a, b, _) = change[j]
			if b in D:
				D[a] = D[b]
			else:
				D[a] = b
			j -= 1
		if arr[i] in D:
			arr[i] = D[arr[i]]
print(*arr)


import sys
input = sys.stdin.readline
n = 0
ans = []
queries = []
for _ in range(int(input())):
	queries.append(tuple(map(int, input().split())))
	if queries[-1][0] == 1:
		ans.append(0)
		n += 1
allNumbers = {i: i for i in range(1, 5 * pow(10, 5) + 1)}
lastIndex = n - 1
for query in range(len(queries) - 1, -1, -1):
	if queries[query][0] == 2:
		allNumbers[queries[query][1]] = allNumbers[queries[query][2]]
	else:
		ans[lastIndex] = allNumbers[queries[query][1]]
		lastIndex -= 1
print(*ans)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
Max = 5 * 100000 + 1
par = [i for i in range(Max)]
q = [list(input().split()) for i in range(int(input()))]
ans = []
while q:
	a = q.pop()
	if a[0] == '1':
		ans.append(par[int(a[1])])
	else:
		par[int(a[1])] = par[int(a[2])]
print(*ans[::-1])


q = int(input())
order = [i for i in range(600000)]
t = [0 for i in range(q)]
x = [0 for i in range(q)]
y = [0 for i in range(q)]
for i in range(q):
	inp = list(map(int, input().split()))
	t[i] = inp[0]
	x[i] = inp[1]
	if inp[0] == 2:
		y[i] = inp[2]
ans = []
for i in range(q - 1, -1, -1):
	if t[i] == 1:
		ans.append(order[x[i]])
	else:
		order[x[i]] = order[y[i]]
print(*ans[::-1])


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
q = I()
l = []
ans = []
for i in range(q):
	l.append(L())
l.reverse()
d = [i for i in range(500001)]
for j in l:
	if j[0] == 1:
		ans.append(d[j[1]])
	else:
		d[j[1]] = d[j[2]]
print(*ans[::-1])


from math import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
from array import array
from re import search
li = lambda : list(map(int, input().split()))
arr = lambda a: array('i', a)
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])
sbstr = lambda a, s: search('.*'.join(a), s)

def solve():
	ans = []
	qre = int(input())
	q = []
	for _ in range(qre):
		q.append(li())
	sw = dict()
	for qr in reversed(q):
		if qr[0] == 1:
			if qr[1] in sw:
				ans.append(sw[qr[1]])
			else:
				ans.append(qr[1])
		elif qr[2] not in sw:
			sw[qr[1]] = qr[2]
		else:
			sw[qr[1]] = sw[qr[2]]
	print(*ans[::-1])
solve()


from sys import stdin, stdout
input = stdin.readline
t = int(input())
store = []
for _ in range(t):
	vals = [int(x) for x in input().split()]
	store.append(vals)
a = []
d = {}
for vals in store[::-1]:
	if vals[0] == 1:
		a.append(d.get(vals[1], vals[1]))
	else:
		d[vals[1]] = d.get(vals[2], vals[2])
print(*a[::-1])


import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict, Counter
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math

def I():
	return int(input())

def lint():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
import heapq

def ask(a, b, c):
	print(f'? {a} {b} {c}')
	sys.stdout.flush()
	res = int(input())
	sys.stdout.flush()
	return res
t = I()
l = []
for _ in range(t):
	l.append(lint())
d = defaultdict(lambda : None)
a = defaultdict(lambda : 0)
l = l[::-1]
ans = []
for i in range(t):
	tmp = l[i]
	if tmp[0] == 1:
		if d[tmp[1]] != None:
			ans.append(a[d[tmp[1]]])
		else:
			ans.append(tmp[1])
	else:
		(x, y) = tmp[1:]
		if d[y] != None:
			a[i] = a[d[y]]
		else:
			a[i] = y
		d[x] = i
print(*ans[::-1])


import sys
input = sys.stdin.readline
mod = 998244353

def power(num, ex):
	(pw, res) = (num, 1)
	while ex:
		if ex & 1:
			res = res * pw
		pw = pw * pw
		ex >>= 1
	return res

def power_with_modulo(num, ex):
	(pw, res) = (num % mod, 1)
	while ex:
		if ex & 1:
			res = res * pw % mod
		pw = pw * pw % mod
		ex >>= 1
	return res
q = int(input())
ans = []
mp = {}
queries = []
while q:
	a = list(map(int, input().split()))
	queries.append(a)
	q -= 1
queries.reverse()
for a in queries:
	if a[0] == 1:
		x = a[1]
		if x in mp.keys():
			ans.append(mp[x])
		else:
			ans.append(x)
	else:
		(x, y) = (a[1], a[2])
		if y in mp.keys():
			mp[x] = mp[y]
		else:
			mp[x] = y
	q -= 1
print(*ans[::-1])


replaces = {}
q = int(input())
requests = [input() for i in range(q)]
ans = []
for r in requests[::-1]:
	if r[0] == '1':
		v = int(r[2:])
		ans.append(replaces.get(v, v))
	else:
		(u, w) = map(int, r[2:].split())
		replaces[u] = replaces.get(w, w)
print(*ans[::-1])


t = int(input())
d = dict()
ans = []
q = []
for i in range(t):
	q.append(list(map(int, input().split())))
for x in reversed(q):
	if x[0] == 1:
		if x[1] not in d:
			cur = x[1]
		else:
			cur = d[x[1]]
		ans.append(cur)
	elif x[2] not in d:
		d[x[1]] = x[2]
	else:
		d[x[1]] = d[x[2]]
print(*ans[::-1])


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return int(input())

def inps():
	return input().strip()

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
n = inp()
l = []
for i in range(n):
	c = inlt()
	t = c[0]
	if t == 1:
		x = c[1]
		l.append([x, 0])
	else:
		(x, y) = (c[1], c[2])
		l.append([x, y])
cont = [n + 1 for i in range(5 * 10 ** 5 + 1)]
val = [0 for i in range(n + 1)]
dp = [0 for i in range(n + 1)]
for i in range(n - 1, -1, -1):
	if l[i][1] == 0:
		if cont[l[i][0]] == n + 1:
			dp[i] = l[i][0]
		else:
			dp[i] = val[cont[l[i][0]]]
	else:
		if cont[l[i][1]] == n + 1:
			val[i] = l[i][1]
		else:
			val[i] = val[cont[l[i][1]]]
		cont[l[i][0]] = i
ans = []
for i in range(n):
	if l[i][1] == 0:
		ans.append(dp[i])
print(*ans)


from sys import stdin, stdout, setrecursionlimit
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappop, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sumx = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
a = []
p = [i for i in range(5 * 10 ** 5 + 1)]
for i in [L() for i in range(I())][::-1]:
	if i[0] == 1:
		a += (p[i[1]],)
	else:
		p[i[1]] = p[i[2]]
print(*a[::-1])


q = int(input())
locations = dict()
n = 0
for i in range(q):
	case = list(map(int, input().split()))
	(x, y) = (0, 0)
	if case[0] == 1:
		x = case[1]
		current = locations.get(x, list())
		current.append(n)
		locations[x] = current
		n += 1
	else:
		(x, y) = (case[1], case[2])
		if x == y:
			continue
		xloc = locations.get(x, list())
		if len(xloc) == 0:
			continue
		locations.pop(x)
		yloc = locations.get(y, list())
		if len(yloc) == 0:
			locations[y] = xloc
		elif len(yloc) > len(xloc):
			yloc.extend(xloc)
			locations[y] = yloc
		else:
			xloc.extend(yloc)
			locations[y] = xloc
output = [0 for i in range(n)]
for (key, value) in locations.items():
	for val in value:
		output[val] = str(key)
print(' '.join(output))


from collections import *
import sys
input = sys.stdin.readline
q = int(input())
r = []
s = {}
for _ in range(q):
	l = list(map(int, input().split()))
	r.append(l)
a = []
for t in reversed(r):
	if t[0] == 2:
		if t[2] not in s:
			s[t[1]] = t[2]
		else:
			s[t[1]] = s[t[2]]
	else:
		a.append(s[t[1]] if t[1] in s else t[1])
print(' '.join(map(str, reversed(a))))


import sys
tokens = ''.join(sys.stdin.readlines()).split()[::-1]

def next():
	return tokens.pop()

def nextInt():
	return int(next())

def nextFloat():
	return float(next())

def getIntArray(n):
	return [nextInt() for _ in range(n)]

def getFloatArray(n):
	return [nextFloat() for _ in range(n)]

def getStringArray(n):
	return [next() for _ in range(n)]
l = 0
map = {}
testcase = True

def solve(testcase=1):
	global l
	if nextInt() == 1:
		ele = nextInt()
		if ele not in map:
			map[ele] = []
		map[ele].append(l)
		l += 1
	else:
		(find, replace) = (nextInt(), nextInt())
		if find not in map or find == replace:
			return
		elif replace not in map:
			map[replace] = []
		(a, b) = (map[find], map[replace]) if len(map[find]) > len(map[replace]) else (map[replace], map[find])
		a += b
		map[replace] = a
		del map[find]
if testcase is None:
	testcaseCount = 1
	while tokens:
		solve(testcaseCount)
		testcaseCount += 1
else:
	testcaseCount = nextInt() if testcase else 1
	for tc in range(testcaseCount):
		solve(tc + 1)
	assert not tokens
ans = [None for i in range(l)]
for value in map:
	for idx in map[value]:
		ans[idx] = value
print(*ans)


class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		self.parent[self.find(b)] = self.find(a)

def main():
	q = int(input())
	n = q
	size = 0
	parValue = [-1] * n
	uf = UnionFind(n)
	parIdx = dict()
	for _ in range(q):
		in_ = readIntArr()
		if len(in_) == 2:
			size += 1
			x = in_[1]
			if x in parIdx.keys():
				uf.union(size - 1, parIdx[x])
				newPar = uf.find(size - 1)
				parIdx[x] = newPar
				parValue[newPar] = x
			else:
				parIdx[x] = size - 1
				parValue[size - 1] = x
		else:
			(x, y) = (in_[1], in_[2])
			if x == y:
				continue
			if x in parIdx.keys():
				xPar = parIdx[x]
				del parIdx[x]
				if y in parIdx.keys():
					yPar = parIdx[y]
					uf.union(xPar, yPar)
					newPar = uf.find(yPar)
					parIdx[y] = newPar
					parValue[newPar] = y
				else:
					parIdx[y] = xPar
					parValue[xPar] = y
	ans = [-1] * size
	for i in range(size):
		value = parValue[uf.find(i)]
		ans[i] = value
	oneLineArrayPrint(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
	print('? {} {} {}'.format(a, b, c))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ansArr):
	print('! {}'.format(' '.join([str(x) for x in ansArr])))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
	main()


lines = int(input())
result = []
tmp = {}
l = []
for _ in range(lines):
	l.append([int(i) for i in input().split()])
for i in reversed(l):
	if i[0] == 1:
		x = i[1]
		if x in tmp:
			result.append(tmp[x])
		else:
			result.append(x)
	else:
		x = i[1]
		y = i[2]
		if y in tmp:
			tmp[x] = tmp[y]
		else:
			tmp[x] = y
print(' '.join([str(i) for i in result[::-1]]))


import sys
input = lambda : sys.stdin.readline().strip()
intput = lambda : map(int, input().split())
(A, queries) = ([], [])
f = [i for i in range(500001)]
(Q,) = intput()
for _ in range(Q):
	q = tuple(intput())
	queries.append(q)
for q in reversed(queries):
	if q[0] == 1:
		A.append(f[q[1]])
	if q[0] == 2:
		f[q[1]] = f[q[2]]
print(*A[::-1])


import sys
input = sys.stdin.readline
q = int(input())
query = [list(map(int, input().split())) for _ in range(q)]
query.reverse()
ans = []
from collections import defaultdict
D = defaultdict(lambda : -1)

def d(x):
	if D[x] == -1:
		return x
	else:
		return D[x]
for i in range(q):
	tq = query[i]
	if tq[0] == 2:
		(x, y) = tq[1:]
		D[x] = d(y)
	else:
		x = d(tq[1])
		ans.append(x)
ans.reverse()
print(*ans)


num_queries = int(input())
queries = []
for _ in range(num_queries):
	queries.append(input())
changes = {}
res = []
for query in queries[::-1]:
	if query[0] == '2':
		(key, value) = map(int, query[2:].split())
		if value in changes:
			changes[key] = changes[value]
		else:
			changes[key] = value
	elif query[0] == '1':
		num = int(query[2:])
		if num in changes:
			num = changes[num]
		res.append(num)
print(*res[::-1])


import sys
input = sys.stdin.readline

def sol():
	ans = []
	queries = []
	allNumbers = {}
	for _ in range(int(input())):
		queries.append(tuple(map(int, input().split())))
		if queries[-1][0] == 1:
			allNumbers[queries[-1][1]] = queries[-1][1]
			ans.append(0)
		else:
			allNumbers[queries[-1][1]] = queries[-1][1]
			allNumbers[queries[-1][2]] = queries[-1][2]
	lastIndex = len(ans) - 1
	for query in range(len(queries) - 1, -1, -1):
		if queries[query][0] == 2:
			allNumbers[queries[query][1]] = allNumbers[queries[query][2]]
		else:
			ans[lastIndex] = allNumbers[queries[query][1]]
			lastIndex -= 1
	print(*ans)
sol()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
	q = int(input())
	ori = []
	op = []
	groups = []
	for _ in range(q):
		temp = list(map(int, input().split()))
		if len(temp) == 2:
			ori.append(temp[1])
		else:
			op.append([len(ori), temp[1], temp[2]])
	op = op[::-1]
	dic = {}
	ans = []

	def change(e, r):
		if r not in dic:
			dic[e] = r
		else:
			dic[e] = dic[r]
	index = 0
	for i in range(len(ori) - 1, -1, -1):
		while index < len(op) and op[index][0] > i:
			change(op[index][1], op[index][2])
			index += 1
		if ori[i] not in dic:
			ans.append(ori[i])
		else:
			ans.append(dic[ori[i]])
	ans = ans[::-1]
	print(*ans)
T = 1
t = 1
while t <= T:
	main(t)
	t += 1


import sys
input = sys.stdin.readline
p = list(range(5 * 10 ** 5 + 1))
arg = []
q = int(input())
s = []
for _ in range(q):
	arg.append(list(map(int, input().split())))
arg.reverse()
for i in range(q):
	if arg[i][0] == 1:
		s.append(p[arg[i][1]])
	else:
		p[arg[i][1]] = p[arg[i][2]]
s.reverse()
print(*s)


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import defaultdict

def main():
	q = int(input())
	cur = 0
	D = defaultdict(lambda : [])
	for i in range(q):
		temp = list(map(int, input().split()))
		if temp[0] == 1:
			x = temp[1]
			D[x].append(cur)
			cur += 1
		else:
			(x, y) = temp[1:]
			if x == y:
				continue
			lx = D[x]
			ly = D[y]
			if len(ly) >= len(lx):
				for j in lx:
					D[y].append(j)
				D.pop(x)
			else:
				for j in ly:
					D[x].append(j)
				D[y] = D[x]
				D.pop(x)
	ans = [0] * cur
	for (k, l) in D.items():
		for i in l:
			ans[i] = k
	print(*ans)
main()


import sys
t = int(input())
m = []
d = {}
from collections import deque
ans = []
for _ in range(t):
	m.append(list(sys.stdin.readline().split()))
for i in range(t - 1, -1, -1):
	if m[i][0] == '1':
		if m[i][1] in d:
			ans.append(d[m[i][1]])
		else:
			ans.append(m[i][1])
	elif m[i][2] in d:
		d[m[i][1]] = d[m[i][2]]
	else:
		d[m[i][1]] = m[i][2]
for i in range(len(ans) - 1, -1, -1):
	print(ans[i], end=' ')


import sys

def rl():
	return sys.stdin.readline()

def r_arr():
	a = rl().split(' ')
	a = [int(x) for x in a]
	return a
n = int(rl())
a = [0] * n
b = [0] * n
x = [0] * n
y = [0] * n
d = {}
for i in range(n):
	arr = r_arr()
	b[i] = arr[0]
	if b[i] == 1:
		a[i] = arr[1]
	else:
		x[i] = arr[1]
		y[i] = arr[2]
for i in range(n - 1, -1, -1):
	if b[i] == 1:
		z = a[i]
		if z in d:
			a[i] = d[z]
	else:
		xx = x[i]
		yy = y[i]
		if yy in d:
			d[xx] = d[yy]
		else:
			d[xx] = yy
st = ''
for i in range(n):
	if b[i] == 1:
		st += str(a[i]) + ' '
print(st)


from sys import stdin
input = stdin.readline

def answer():
	(count, take) = (0, [])
	for i in range(q):
		s = input().split()
		opp = int(s[0])
		if opp == 1:
			x = int(s[1])
			take.append([1, x, x])
			count += 1
		else:
			(x, y) = (int(s[1]), int(s[2]))
			take.append([0, x, y])
	(d, ans) = (dict(), [])
	for i in range(q - 1, -1, -1):
		(opp, x, y) = take[i]
		if opp == 1:
			ans.append(d.get(x, x))
		d[x] = d.get(y, y)
	ans = ans[::-1]
	return ans
for T in range(1):
	q = int(input())
	print(*answer())


import sys
input = sys.stdin.readline
parent = [i for i in range(500001)]
q = []
for _ in range(int(input())):
	q.append(tuple(map(int, input().split())))
q.reverse()
ans = []
for j in q:
	if j[0] == 1:
		ans.append(parent[j[1]])
	else:
		parent[j[1]] = parent[j[2]]
ans.reverse()
print(*ans)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
sys.setrecursionlimit(3 * 10 ** 5)
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
x = 0
pref = []
lvl = []
gp = []
ans = []
f = 0
w = []

def dfs(i, prod, rem, n):
	if rem == 0:
		while i < len(n):
			prod *= int(n[i])
			i += 1
		return prod
	if i == len(n):
		return prod
	mx = 0
	for j in range(9 - int(n[i])):
		mx = max(dfs(i + 1, (int(n[i]) + min(j, rem)) * prod, rem - min(j, rem), n), mx)
	return mx

class Disjoint_SU:

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

	def lake_de(self, a):
		if a == self.parent[a]:
			return a
		self.parent[a] = self.lake_de(self.parent[a])
		return self.parent[a]

	def jod(self, a, b):
		x = self.lake_de(a)
		y = self.lake_de(b)
		if x == y:
			return True
		if self.size[x] > self.size[y]:
			self.size[x] += self.size[y]
			self.parent[y] = x
		else:
			self.size[y] += self.size[x]
			self.parent[x] = y
		return False

def hnbhai(tc):
	n = sb()
	q = []
	for i in range(n):
		q.append(sd())
	parent = [i for i in range(5 * 10 ** 5 + 5)]
	tot = []
	for i in range(n - 1, -1, -1):
		if q[i][0] == 1:
			tot.append(parent[q[i][1]])
		else:
			parent[q[i][1]] = parent[q[i][2]]
	print(*tot[::-1])
	return
for _ in range(1):
	hnbhai(_ + 1)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import math
import bisect
mp = [i for i in range(5 * 10 ** 5 + 1)]
res = []
l = []
t = int(input())
for a0 in range(t):
	inp = [int(i) for i in input().split()]
	l.append(inp)
for i in range(t - 1, -1, -1):
	if len(l[i]) == 2:
		res.append(mp[l[i][1]])
	else:
		mp[l[i][1]] = mp[l[i][2]]
res.reverse()
print(*res)


import sys
t = int(sys.stdin.readline())
ans = []
count = 0
dp = [[] for _ in range(5 * 10 ** 5 + 1)]
for i in range(t):
	A = list(map(int, sys.stdin.readline().split()))
	if A[0] == 1:
		x = A[1]
		dp[x].append(count)
		ans.append(x)
		count += 1
	else:
		x = A[1]
		y = A[2]
		if x == y:
			continue
		if len(dp[y]) < len(dp[x]):
			(dp[x], dp[y]) = (dp[y], dp[x])
		for d in dp[x]:
			dp[y].append(d)
		dp[x].clear()
for x in range(5 * 10 ** 5 + 1):
	for d in dp[x]:
		ans[d] = x
print(*ans)


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

def bootstrap(f, stack=[]):

	def fun(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return fun

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
from collections import deque
q = int(input())
ans = []
req = []
for i in range(q):
	b = list(map(int, input().split()))
	req.append(b)
val = [i for i in range(500001)]
j = q - 1
while j >= 0:
	curr = req[j]
	if curr[0] == 2:
		val[curr[1]] = val[curr[2]]
	else:
		ans.append(val[curr[1]])
	j += -1
ans = ans[::-1]
print(*ans)


from __future__ import print_function
from math import *
from collections import deque
import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())

class node:

	def __init__(self, next, value):
		self.value = value
		self.next = next
q = inp()
d = {}
c = 0
tail = {}
for i in range(q):
	x = inlt()
	if x[0] == 1:
		if x[1] not in d:
			d[x[1]] = node(None, c)
			tail[x[1]] = d[x[1]]
			c += 1
		else:
			d[x[1]] = node(d[x[1]], c)
			c += 1
	else:
		if x[1] == x[2]:
			continue
		if x[1] in d:
			if x[2] in d:
				tail[x[2]].next = d[x[1]]
				tail[x[2]] = tail[x[1]]
				d.pop(x[1])
			else:
				d[x[2]] = d[x[1]]
				tail[x[2]] = tail[x[1]]
				d.pop(x[1])
out = [-1] * c
for i in d:
	cur = d[i]
	while cur != None:
		out[cur.value] = i
		cur = cur.next
print(*out)


from collections import *
import sys
import io, os
import math
from heapq import *
gcd = math.gcd
sqrt = math.sqrt

def ceil(a, b):
	a = -a
	k = a // b
	k = -k
	return k
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def strinp(testcases):
	k = 5
	if testcases == -1 or testcases == 1:
		k = 1
	f = str(input())
	f = f[2:len(f) - k]
	return f

def main():
	q = int(input())
	ans = []
	iden = [i for i in range(5 * 10 ** 5 + 1)]
	quer = []
	for _ in range(q):
		arr = list(map(int, input().split()))
		quer.append(arr)
	arr = []
	for i in range(q - 1, -1, -1):
		if quer[i][0] == 1:
			arr.append(iden[quer[i][1]])
			continue
		iden[quer[i][1]] = iden[quer[i][2]]
	arr.reverse()
	print(*arr)
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
import math
import collections
from itertools import permutations
from itertools import combinations

def prob():
	n = int(input())
	qu = []
	while n > 0:
		l = [int(x) for x in input().split()]
		qu.append(l)
		n -= 1
	di = dict()
	qu.reverse()
	ans = []
	for i in qu:
		if i[0] == 1:
			ans.append(di.get(i[1], i[1]))
		else:
			di[i[1]] = di.get(i[-1], i[-1])
	ans.reverse()
	print(*ans)
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = 1
for _ in range(0, t):
	prob()


import sys

def replace_the_number(q, queries):
	output = []
	transformations = {}
	for i in range(q - 1, -1, -1):
		query = queries[i]
		if query[0] == '1':
			value = int(query[2:])
			value = transformations.get(value, value)
			output += [value]
		else:
			(x, y) = map(int, query[2:].split())
			if y in transformations:
				transformations[x] = transformations[y]
			else:
				transformations[x] = y
	output = output[::-1]
	return ' '.join(map(str, output))
q = int(input())
queries = [None] * q
for i in range(q):
	queries[i] = input()
sys.stdout.write(f'{replace_the_number(q, queries)}\n')


import sys
input = sys.stdin.readline
mod = 998244353

def power(num, ex):
	(pw, res) = (num, 1)
	while ex:
		if ex & 1:
			res = res * pw
		pw = pw * pw
		ex >>= 1
	return res

def power_with_modulo(num, ex):
	(pw, res) = (num % mod, 1)
	while ex:
		if ex & 1:
			res = res * pw % mod
		pw = pw * pw % mod
		ex >>= 1
	return res
n = 5 * 10 ** 5 + 1
q = int(input())
mp = [[] for i in range(n)]
idx = 0
for _ in range(q):
	a = list(map(int, input().split()))
	if a[0] == 1:
		x = a[1]
		mp[x].append(idx)
		idx += 1
	else:
		(x, y) = (a[1], a[2])
		if x != y:
			if len(mp[x]) > len(mp[y]):
				(mp[x], mp[y]) = (mp[y], mp[x])
			for i in mp[x]:
				mp[y].append(i)
			mp[x].clear()
ans = [None] * idx
for i in range(n):
	for you in mp[i]:
		ans[you] = i
print(*ans)


a = []
for _ in range(int(input())):
	g = [int(x) for x in input().split()]
	a.append(g)
a = a[::-1]
d = {}
res = []
for q in a:
	if len(q) == 2:
		if q[1] in d.keys():
			res.append(str(d[q[1]]))
		else:
			res.append(str(q[1]))
	else:
		y = q[2]
		x = q[1]
		if y in d:
			d[x] = d[y]
		else:
			d[x] = y
print(' '.join(res[::-1]))


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
try:
	(sys.stdin, sys.stdout) = (open('in.txt', 'r'), open('out.txt', 'w'))
except:
	pass
ii1 = lambda : int(sys.stdin.readline().strip())
is1 = lambda : sys.stdin.readline().strip()
iia = lambda : list(map(int, sys.stdin.readline().strip().split()))
isa = lambda : sys.stdin.readline().strip().split()
mod = int(1000000000.0 + 7)
from math import inf
from collections import defaultdict as dd

def main(t):
	idx = 0
	dic = dd(list)
	for _ in range(ii1()):
		arr = iia()
		if arr[0] == 1:
			x = arr[1]
			dic[x].append(idx)
			idx += 1
		else:
			x = arr[1]
			y = arr[2]
			if x in dic and x != y:
				n1 = len(dic[x])
				n2 = len(dic[y])
				if n1 > n2:
					curr = dic[y]
					dic[y] = dic[x]
					dic[y].extend(curr)
					del dic[x]
				else:
					dic[y].extend(dic.pop(x))
	ans = [None] * idx
	for key in dic:
		for i in dic[key]:
			ans[i] = key
	print(*ans)
t = 1
for _ in range(t):
	main(_)


import sys
from collections import deque
import math
from bisect import bisect_left
from functools import cmp_to_key

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

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

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

def SI():
	return sys.stdin.readline().strip()

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
a = []
ans = []
for _ in range(II()):
	s = input().split()
	t = int(s.pop(0))
	if t == 1:
		x = int(s[0])
		a.append((x, -1))
	else:
		(x, y) = s
		x = int(x)
		y = int(y)
		a.append((x, y))
d = {}
a.reverse()
for (x, y) in a:
	if y == -1:
		if not d.get(x):
			ans.append(x)
		else:
			ans.append(d[x])
	elif d.get(y):
		d[x] = d[y]
	else:
		d[x] = y
ans.reverse()
print(*ans)


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]
INF = 10 ** 10
Q = int(input())
Query = []
for _ in range(Q):
	dat = list(map(int, input().split()))
	Query.append(dat)
Table = list(range(5 * 10 ** 5 + 1))
result = []
for query in reversed(Query):
	if query[0] == 1:
		x = query[1]
		result.append(Table[x])
	else:
		(x, y) = (query[1], query[2])
		Table[x] = Table[y]
print(*reversed(result))


q = int(input())
queries = []
for i in range(q):
	queries.append([int(x) for x in input().split()])
queries.reverse()
perm = [0] * 500005
for i in range(500005):
	perm[i] = i
ans = []
for query in queries:
	if query[0] == 1:
		ans.append(perm[query[1]])
	else:
		perm[query[1]] = perm[query[2]]
ans.reverse()
print(*ans)


from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math

def inp(force_list=False):
	re = list(map(int, input().split()))
	if len(re) == 1 and (not force_list):
		return re[0]
	return re

def inst():
	return input().strip()

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
MOD = 998244353

def query(a, b, c):
	print('! %d %d %d' % (a + 1, b + 1, c + 1))
	stdout.flush()
	return inp()

def merge(a, b):
	if len(a) < len(b):
		(a, b) = (b, a)
	a.extend(b)
	return a

def my_main():
	kase = 1
	pans = []
	for _ in range(kase):
		q = inp()
		mp = defaultdict(list)
		idx = 0
		for i in range(q):
			qq = inp()
			if qq[0] == 1:
				mp[qq[1]].append(idx)
				idx += 1
			else:
				(x, y) = qq[1:]
				if x != y:
					mp[y] = merge(mp[y], mp[x])
					mp.pop(x, None)
		ans = [0] * idx
		for (k, v) in mp.items():
			for idx in v:
				ans[idx] = k
		pans.append(' '.join(map(str, ans)))
	print('\n'.join(pans))
my_main()


n = int(input())
mapIndex = {}
arr = []
for i in range(n):
	inpArr = [int(x) for x in input().split()]
	if inpArr[0] == 1:
		arr.append(inpArr[1])
	else:
		arr.append(inpArr[1:])
ans = []
for i in arr[::-1]:
	if isinstance(i, list):
		if i[1] not in mapIndex:
			mapIndex[i[1]] = i[1]
		if i[0] not in mapIndex:
			mapIndex[i[0]] = i[0]
		mapIndex[i[0]] = mapIndex[i[1]]
	else:
		if i not in mapIndex:
			mapIndex[i] = i
		ans.append(str(mapIndex[i]))
print(' '.join(ans[::-1]))


T = 1

def solve():
	positions = {}
	cnt_numbers = 0
	n = int(input())
	for i in range(n):
		line = list(map(int, input().split()))
		if line[0] == 1:
			x = line[1]
			if not x in positions:
				positions[x] = []
			positions[x] += [cnt_numbers]
			cnt_numbers += 1
		else:
			x = line[1]
			y = line[2]
			if y not in positions:
				positions[y] = []
			if y == x:
				continue
			if x in positions:
				if len(positions[x]) > len(positions[y]):
					positions[x] += positions[y]
					positions[y] = positions[x]
				else:
					positions[y] += positions[x]
				del positions[x]
	answer = [0] * cnt_numbers
	for numb in positions:
		for i in positions[numb]:
			answer[i] = numb
	return ' '.join([str(x) for x in answer])
for t in range(T):
	print(solve())


import sys

def input():
	return sys.stdin.readline()[:-1]
Q = int(input())
queries = [list(map(int, input().split())) for i in range(Q)]
queries = queries[::-1]
ans = []
S = {}

def d(x):
	if x in S:
		return S[x]
	else:
		return x
for que in queries:
	if que[0] == 1:
		ans.append(d(que[1]))
	else:
		S[que[1]] = d(que[2])
print(*ans[::-1])


from sys import stdin, stdout
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
d = []
q = int(input())
ls = []
for i in range(q):
	ls.append(list(map(int, input().split())))
for i in range(500005):
	d.append(i)
ans = []
for i in range(q - 1, -1, -1):
	if ls[i][0] == 1:
		ans.append(d[ls[i][1]])
	else:
		d[ls[i][1]] = d[ls[i][2]]
stdout.write(' '.join(map(str, reversed(ans))) + '\n')


def main():
	q = int(input())
	indexes = [[] for __ in range(500005)]
	i = 0
	for _ in range(q):
		zz = readIntArr()
		if zz[0] == 1:
			indexes[zz[1]].append(i)
			i += 1
		else:
			x = zz[1]
			y = zz[2]
			if x == y or len(indexes[x]) == 0:
				continue
			if len(indexes[x]) < len(indexes[y]):
				arr1 = indexes[x]
				arr2 = indexes[y]
			else:
				arr1 = indexes[y]
				arr2 = indexes[x]
			for z in arr1:
				arr2.append(z)
			indexes[x] = []
			indexes[y] = arr2
	ans = [-1] * i
	for (k, v) in enumerate(indexes):
		for i in v:
			ans[i] = k
	oneLineArrayPrint(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
	print('? {} {} {}'.format(a, b, c))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ansArr):
	print('! {}'.format(' '.join([str(x) for x in ansArr])))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
	main()


ql = []
for tt in range(int(input())):
	ql.append(input())
l = []
d = [-1] * 1000000
for tt in range(1, len(ql) + 1):
	q = list(map(int, ql[-tt].split()))
	if len(q) == 2:
		if d[q[1]] == -1:
			l.append(q[1])
		else:
			l.append(d[q[1]])
	elif d[q[2]] == -1:
		d[q[1]] = q[2]
	else:
		d[q[1]] = d[q[2]]
for i in range(1, len(l) + 1):
	print(l[-i], end=' ')


import sys
par = [i for i in range(500001)]

def calc(n, q):
	ans = []
	i = len(q) - 1
	while i >= 0:
		if len(q[i]) == 2:
			x = q[i][1]
			ans.append(par[x])
		else:
			x = q[i][1]
			y = q[i][2]
			par[x] = par[y]
		i -= 1
	ans = ans[::-1]
	return ans

def solve():
	q = int(sys.stdin.readline())
	a = list((tuple(map(int, sys.stdin.readline().split())) for _ in range(q)))
	res = calc(q, a)
	print(*res)
solve()


from collections import defaultdict
from sys import stdin, stdout
d = defaultdict(list)
length = 0
for _ in range(int(stdin.readline())):
	(n, *rest) = map(int, stdin.readline().split())
	if n == 1:
		d[rest[0]].append(length)
		length += 1
	elif n == 2:
		if rest[0] != rest[1]:
			if len(d[rest[1]]) > len(d[rest[0]]):
				d[rest[1]].extend(d[rest[0]])
			else:
				d[rest[0]].extend(d[rest[1]])
				d[rest[1]] = d[rest[0]]
			d[rest[0]] = list()
arr = [0] * length
for num in d:
	for index in d[num]:
		arr[index] = str(num)
stdout.write(' '.join(arr))


import sys
input = sys.stdin.readline

class Node:

	def __init__(self, val):
		self.val = val
		self.next = None
n = int(input())
cnt = 0
d = {}
g = {}
for i in range(n):
	l = list(map(int, input().split()))
	if len(l) == 2:
		x = l[1]
		now = Node(cnt)
		if x in d and d[x] != None:
			d[x].next = now
			d[x] = d[x].next
		else:
			d[x] = now
			g[x] = now
		cnt += 1
	else:
		(x, y) = (l[1], l[2])
		if x not in d or d[x] == None:
			continue
		if x == y:
			continue
		if y in d and d[y] != None:
			d[y].next = g[x]
			d[y] = d[x]
		else:
			d[y] = d[x]
			g[y] = g[x]
		d[x] = None
		g[x] = None
ans = [0 for i in range(cnt)]
for x in g:
	while g[x] != None:
		ans[g[x].val] = x
		g[x] = g[x].next
print(*ans)


import sys
q = int(sys.stdin.readline())
f = list(range(500001))
dd = [0] * 500001

def find(i):
	if i != f[i]:
		f[i] = find(f[i])
	return f[i]

def union(i, j):
	(fi, fj) = (find(i), find(j))
	if fi != fj:
		if dd[fi] < dd[fj]:
			f[fi] = fj
		else:
			f[fj] = fi
		if dd[fi] == dd[fj]:
			dd[fi] += 1
mp = {}
n = 0
arr = []
for _ in range(q):
	op = list(map(int, sys.stdin.readline().split()))
	if op[0] == 1:
		x = op[1]
		arr.append(x)
		if x in mp:
			union(mp[x], n)
		else:
			mp[x] = n
		n += 1
	else:
		(x, y) = (op[1], op[2])
		if x == y or x not in mp:
			continue
		if y in mp:
			arr[find(mp[x])] = y
			union(mp[x], mp[y])
		else:
			arr[find(mp[x])] = y
			mp[y] = mp[x]
		del mp[x]
for i in range(n):
	arr[i] = arr[find(i)]
print(' '.join(map(str, arr)))


from collections import defaultdict as dd
import math
import sys
input = sys.stdin.readline

def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return map(int, input().split())

def lm():
	return list(map(int, input().split()))

def solve():
	n = nn()
	dlists = dd(list)
	dkeys = dict()
	place = 0
	id_vals = 10 ** 6
	for i in range(n):
		q = lm()
		if q[0] == 1:
			if q[1] in dkeys:
				val = dkeys[q[1]]
				dlists[val].append(place)
			else:
				dkeys[q[1]] = id_vals
				dlists[id_vals].append(place)
				id_vals += 1
			place += 1
		else:
			(x, y) = (q[1], q[2])
			if x == y:
				pass
			elif x in dkeys:
				if y in dkeys:
					yid = dkeys[y]
					xid = dkeys[x]
					ylen = len(dlists[yid])
					xlen = len(dlists[xid])
					if xlen <= ylen:
						dlists[yid].extend(dlists[xid])
						dkeys[y] = yid
					else:
						dlists[xid].extend(dlists[yid])
						dkeys[y] = xid
					del dkeys[x]
				else:
					dkeys[y] = dkeys[x]
					del dkeys[x]
	out = [0 for i in range(place)]
	for (key, value) in dkeys.items():
		nums = dlists[value]
		for num in nums:
			out[num] = key
	print(*out)
q = 1
for _ in range(q):
	solve()


import sys
inpu = sys.stdin.readline
prin = sys.stdout.write
I = lambda : [*map(int, inpu().split())]
(q,) = I()
queries = []
for i in range(q):
	queries.append(I())
final = {}
rev = []
for i in range(q - 1, -1, -1):
	query = queries[i]
	if query[0] == 1:
		if query[1] in final:
			rev.append(final[query[1]])
		else:
			rev.append(query[1])
	else:
		(x, y) = (query[1], query[2])
		if y in final:
			final[x] = final[y]
		else:
			final[x] = y
print(' '.join((str(guy) for guy in rev[::-1])))


import sys
input = sys.stdin.readline
qu = []
qq = int(input())
for _ in range(qq):
	qu.append(list(map(int, input().split())))
si = 500001
ar = [i for i in range(si)]
ans = []
for i in range(qq - 1, -1, -1):
	if qu[i][0] == 1:
		ans.append(ar[qu[i][1]])
	else:
		x = qu[i][1]
		y = qu[i][2]
		ar[x] = ar[y]
print(*ans[::-1])


from sys import stdin

def main():
	q = int(stdin.readline())
	queries = []
	for _ in range(q):
		queries.append(list(map(int, stdin.readline().split())))
	answer = []
	replace = {}
	for query in reversed(queries):
		if query[0] == 1:
			answer.append(replace.get(query[1], query[1]))
		else:
			replace[query[1]] = replace.get(query[2], query[2])
	print(' '.join(map(str, reversed(answer))))
main()


from sys import stdin, stdout
q = int(stdin.readline())
a = [['NIL', 'NIL'] for i in range(500001)]
array_pointer = 0
for _ in range(q):
	content = stdin.readline().split()
	if len(content) == 2:
		x = int(content[1])
		block = [array_pointer, 'NIL']
		array_pointer += 1
		if a[x][0] == 'NIL':
			a[x][0] = block
			a[x][1] = block
		else:
			a[x][1][1] = block
			a[x][1] = block
	else:
		(x, y) = (int(content[1]), int(content[2]))
		if x == y or a[x][0] == 'NIL':
			pass
		elif a[y][0] == 'NIL':
			a[y][0] = a[x][0]
			a[y][1] = a[x][1]
			a[x][0] = 'NIL'
			a[x][1] = 'NIL'
		else:
			a[y][1][1] = a[x][0]
			a[y][1] = a[x][1]
			a[x][0] = 'NIL'
			a[x][1] = 'NIL'
answer = [0] * array_pointer
for i in range(1, 500001):
	pointer = a[i][0]
	while pointer != 'NIL':
		answer[pointer[0]] = str(i)
		pointer = pointer[1]
stdout.write(' '.join(answer) + '\n')


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
q = int(input())
l = 5 * pow(10, 5) + 5
a = [[] for _ in range(l)]
i = 0
for _ in range(q):
	t = list(map(int, input().split()))
	if t[0] == 1:
		x = t[1]
		a[x].append(i)
		i += 1
	else:
		(x, y) = (t[1], t[2])
		if x == y:
			continue
		if len(a[x]) <= len(a[y]):
			while a[x]:
				a[y].append(a[x].pop())
		else:
			while a[y]:
				a[x].append(a[y].pop())
			(a[x], a[y]) = (a[y], a[x])
n = i
ans = [0] * n
for i in range(1, l):
	for j in a[i]:
		ans[j] = i
sys.stdout.write(' '.join(map(str, ans)))


import sys
import math
from collections import deque, Counter
from sys import stdin
int1 = lambda x: int(x) - 1
stinput = lambda : stdin.readline()[:-1]
ii = lambda : int(stinput())
mi = lambda : map(int, stdin.readline().split())
li = lambda : list(mi())
mi1 = lambda : map(int1, stdin.readline().split())
li1 = lambda : list(mi1())
mis = lambda : map(str, stdin.readline().split())
lis = lambda : list(mis())
from collections import defaultdict
import heapq
mod = 10 ** 9 + 7
Mod = 998244353
INF = 10 ** 18
ans = 0
q = ii()
query = []
for i in range(q):
	query.append(li())
ans = []
d = defaultdict(int)
for x in query[::-1]:
	if x[0] == 2:
		(y, z) = (x[1], x[2])
		if z in d:
			d[y] = d[z]
		else:
			d[y] = z
	else:
		y = x[1]
		if y in d:
			ans.append(d[y])
		else:
			ans.append(y)
print(*ans[::-1])


import sys
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue as pq
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
mod = 10 ** 9 + 7
mod1 = 998244353

def get(a):
	if a == parent[a]:
		return a
	parent[a] = get(parent[a[i]])
	return parent[a]
for _ in range(1):
	mx = 5 * 10 ** 5 + 1
	parent = [i for i in range(mx)]
	q = ii()
	a = []
	for i in range(q):
		a.append(il())
	ans = []
	a = a[::-1]
	for i in range(q):
		if a[i][0] == 1:
			ans.append(parent[a[i][1]])
		else:
			parent[a[i][1]] = parent[a[i][2]]
	ans.reverse()
	print(*ans)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()
import bisect, string, math, time, functools, random, fractions
from bisect import *
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, groupby
rep = range
R = range

def I():
	return int(input())

def LI():
	return [int(i) for i in input().split()]

def SLI():
	return sorted([int(i) for i in input().split()])

def LI_():
	return [int(i) - 1 for i in input().split()]

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def NLI(n):
	return [[int(i) for i in input().split()] for i in range(n)]

def NLI_(n):
	return [[int(i) - 1 for i in input().split()] for i in range(n)]

def StoLI():
	return [ord(i) - 97 for i in input()]

def ItoS(n):
	return chr(n + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def RLI(n=8, a=1, b=10):
	return [random.randint(a, b) for i in range(n)]

def RI(a=1, b=10):
	return random.randint(a, b)

def INP():
	N = 10
	n = random.randint(2, N)
	mn = 1
	mx = 5
	a = [random.randint(mn, mx) for i in range(n)]
	s = [random.randint(mn, mx) for i in range(n)]
	return (n, a, s)

def Rtest(T):
	(case, err) = (0, 0)
	for i in range(T):
		inp = INP()
		a1 = naive(*inp)
		a2 = solve(*inp)
		if a1 != a2:
			(x, y) = a1
			(z, w) = a2
			cm = Comb(max(x, z))
			if cm.comb(x, y) == cm.comb(z, w):
				case += 1
				continue
			print(inp)
			print('naive', a1)
			print('solve', a2)
			err += 1
		case += 1
	print('Tested', case, 'case with', err, 'errors')

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			org_inp.append(inp)
		else:
			inp = ls[i]
		if len(inp) == 2:
			(a, b) = inp
			c = 1
		else:
			(a, b, c) = inp
		if index == 1:
			a -= 1
			b -= 1
		aa = (a, c)
		bb = (b, c)
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)

def RE(E):
	rt = [[] for i in range(len(E))]
	for i in range(len(E)):
		for (nb, d) in E[i]:
			rt[nb] += ((i, d),)
	return rt

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}, boundary=1):
	mp = [boundary] * (w + 2)
	found = {}
	for i in R(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [boundary] + [mp_def[j] for j in s] + [boundary]
	mp += [boundary] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def accum(ls):
	rt = [0]
	for i in ls:
		rt += [rt[-1] + i]
	return rt

def bit_combination(n, base=2):
	rt = []
	for tb in R(base ** n):
		s = [tb // base ** bt % base for bt in R(n)]
		rt += [s]
	return rt

def gcd(x, y):
	if y == 0:
		return x
	if x % y == 0:
		return y
	while x % y != 0:
		(x, y) = (y, x % y)
	return y

def YN(x):
	print(['NO', 'YES'][x])

def Yn(x):
	print(['No', 'Yes'][x])

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
mo = 10 ** 9 + 7
mo = 998244353
inf = float('inf')
FourNb = [(-1, 0), (1, 0), (0, 1), (0, -1)]
EightNb = [(-1, 0), (1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
compas = dict(zip('WENS', FourNb))
cursol = dict(zip('LRUD', FourNb))
alp = [chr(ord('a') + i) for i in range(26)]

class UnionFind:

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

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

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

	def union(self, x, y):
		r1 = self._root(x)
		r2 = self._root(y)
		if r1 == r2:
			return
		d1 = self.table[r1]
		d2 = self.table[r2]
		if d1 <= d2:
			self.table[r2] = r1
			if d1 == d2:
				self.table[r1] -= 1
		else:
			self.table[r1] = r2

	def __str__(self):
		rt = [i if j < 0 else j for (i, j) in enumerate(self.table)]
		return str(rt)
show_flg = False
show_flg = True
ans = 0
q = I()
p = []
r = []
o = []
op = []
for _ in range(q):
	(t, x, *y) = LI()
	p += ((t, x, y),)
n = 5 * 10 ** 5 + 1
c = list(range(n + 1))
uf = UnionFind(n)
for (t, x, z) in p[::-1]:
	if t == 2:
		y = z[0]
		uf.union(y, x)
		op += ((x, y),)
		c[x] = c[y]
	else:
		r += (c[x],)
		o += (x,)
		op += (x,)
print(*r[::-1])


from sys import *
input = stdin.readline
lst = []
d = []
ans = []
n = int(input())
d = [0] * 500002
for i in range(500002):
	d[i] = i
for i in range(n):
	lst2 = list(map(int, input().split()))
	lst.append(lst2)
for i in range(n - 1, -1, -1):
	if lst[i][0] == 1:
		ans.append(d[lst[i][1]])
	else:
		d[lst[i][1]] = d[lst[i][2]]
print(*ans[::-1])