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 range(len(s)):
    print(s[i],end=" ")