n,t=map(int,raw_input().strip().split())
sno=map(str,raw_input().strip().split())
for i in range(t):
	n1,n2=map(str,raw_input().strip().split())
	sno.insert(sno.index(n2),n1)
for i in sno:
	print i,
print