n,t=map(int,input().split())
s=input().split()

for i in range(t):
    a=input().split()
    s.insert(s.index(a[1]),a[0])

for i in s:
    print(i,end=" ")
print()