while True:
    try:
        n,t=map(int,input().split())
        lst=input().split()
        for i in range(t):
            index = 0
            x,y=input().split()
            for j in range(len(lst)):
                if lst[j] == y:
                    index = j
                    break
            lst.insert(index, x)
        for m in lst[:-1]:
            print(m,end=" ")
        print(lst[-1])
            
    except EOFError:
        break