n,m = map(int,input().split())
lst = input().split() #原列表

for i in range(m):
    a = input().split()#新的待插入数据和要在谁前面插入
    j = lst.index(a[1])#找到要插入的位置（原列表中的位置）
    lst.insert(j,a[0])#插入到原列表适当位置lst.insert(index,x)将x插入列表lst到中index下标处

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