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

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

for m in lst:
    print(m,end=" ")