n,t=map(int,input().split())
a=list(input().split())
b=[]
for case in range(t):
    b.append(input().split())
count=n
for j in range(len(b)):
    i=0
    while i <=count:
        if b[j][1]==a[i]:
            a.insert(i,b[j][0])
            count=count+1
            break
        i=i+1
s=''
for i in range(len(a)):
    if i==0:
        s=a[0]+' '
    elif i==len(a)-1:
        s=s+a[i]
    else:
        s=s+a[i]+' '        
print(s)