while True:
    try:
        n,t=map(int,input().split())
        s=input().split()
        for i in range(t):
            x,y=input().split()
            j = 0
            while j < n:
                if y == s[j]:
                    if j==0:
                        s=[x]+s
                        n=n+1
                    else:
                        s=s[0:j]+[x]+s[j:]
                        n=n+1
                    break
                j = j + 1
        for nn in s:
            print(nn, end=" ")
        print()
    except EOFError:
        break