class Node: __slots__ = ("val", "pre", "next") def __init__(self, val: str): self.val: str = val self.pre: "Node" = None self.next: "Node" = None def insert_before(target: Node, node: Node): # 删除node node.pre.next = node.next node.next.pre = node.pre # 插入到target前面 node.pre = target.pre node.next = target target.pre.next = node target.pre = node def main(): n, m = list(map(int, input().split())) names = input().split() head = Node(None) tail = Node(None) head.next = tail tail.pre = head dic = {} cur = head # 构建链表 for name in names: node = Node(name) dic[name] = node cur.next = node node.pre = cur cur = node cur.next = tail tail.pre = cur # 依次处理各个插队事件 for _ in range(m): a, b = input().split() anode, bnode = dic[a], dic[b] if anode.next == bnode: continue else: insert_before(bnode, anode) result = [] cur = head.next while cur != tail: result.append(cur.val) cur = cur.next print(" ".join(result)) if __name__ == "__main__": main()