题解 | 插队

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()