#-*-coding:utf-8-*-
n,t=map(int,raw_input().strip().split())

st=raw_input().strip().split()
a=[]
b=[]
for i in range(t):
	s=raw_input().strip().split()
	a.append(s[0])
	b.append(s[1])
for i in range(t):
	#x=st.find(a[i])#字符串才有find
	x=st.index(b[i])
	st.insert(x,a[i])
for v in st:
	print v,