n,t = map(int, input().split())
a = list(input().split())
for i in range(t):
	x, y = map(str, input().split())
	a.insert(a.index(y), x)
for i in a:
	print(i, end = " ") 
print()