题解 | 插队

n, m = map(int, input().split())
ls = input().split()

# 维护前后关系，双向链表结构
prev = {}
next = {}

for i in range(n):
    if i > 0:
        prev[ls[i]] = ls[i - 1]
    else:
        prev[ls[i]] = None
    if i < n - 1:
        next[ls[i]] = ls[i + 1]
    else:
        next[ls[i]] = None

head = ls[0]

for _ in range(m):
    a, b = input().split()
    if a == b:
        continue
    # 移除 a
    pre_a, nex_a = prev[a], next[a]
    if pre_a:
        next[pre_a] = nex_a
    else:
        head = nex_a
    if nex_a:
        prev[nex_a] = pre_a

    # 插入 a 到 b 前面
    pre_b = prev[b]
    if pre_b:
        next[pre_b] = a
    else:
        head = a
    prev[a] = pre_b
    next[a] = b
    prev[b] = a

# 从头输出
res = []
cur = head
while cur:
    res.append(cur)
    cur = next[cur]

print(*res)