n,t=map(int,input().split())
lst=[]
lst= list(input().split())
##print(lst)
for n in range(t):
    a,b=map(str,input().split())
    lst.insert(lst.index(b), a)
##print(lst)
##for m in lst[:-1]:
##    print(m,end=" ")
##print(lst[-1])

print( ' '.join(lst))