分数: 1000 点
问题陈述
给你一个排列 P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) 和一组整数对 S = \lbrace (x_1, y_1), (x_2, y_2), \ldots, (x_M, y_M) \rbrace.
您可以按任意顺序执行任意次数的以下两种类型的操作。
- 选择 (l, r)\ (1 \leq l < r \leq N) 这样 (P_l, P_r) \in S or (P_r, P_l) \in S,并交换 l-th 和 r第一个元素 P。也就是说,替换 P 与 (P_1, \ldots, P_{l-1}, P_r, P_{l+1}, \ldots, P_{r-1}, P_l, P_{r+1}, \ldots, P_N).
- 选择 (l, r)\ (1 \leq l < r \leq N) 这样 (P_l, P_r) \in S or (P_r, P_l) \in S,并反转元素 l-第 r-第 P。也就是说,替换 P 与 (P_1, \ldots, P_{l-1}, P_r, P_{r-1}, \ldots, P_{l+1}, P_l, P_{r+1}, \ldots, P_N).
找到通过操作可获得的按字典顺序排列的最小排列。
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1 \leq T \leq 3 \times 10^4
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- P 是一个排列 (1, 2, \ldots, N).
- 1 \leq x_i < y_i \leq N
- (x_i, y_i) \neq (x_j, y_j) if i \neq j.
- 总和 N 所有测试用例最多 2 \times 10^5.
- 总和 M 所有测试用例最多 2 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N M P_1 P_2 \ldots P_N x_1 y_1 x_2 y_2 \vdots x_M y_M
输出
输出 T 行。的 i- 第行应包含以下问题的答案 \mathrm{case}_i.
示例输入 1
2 6 2 1 3 2 5 4 6 1 4 2 5 8 5 7 3 2 8 6 5 1 4 1 8 2 5 3 4 7 8 5 6
示例输出 1
1 2 5 3 4 6 1 2 3 7 5 6 8 4
对于第一个测试用例,您可以获得 P = (1, 2, 5, 3, 4, 6) 通过执行如下操作。
- 最初, P = (1, 3, 2, 5, 4, 6).
- 将第一个元素反转到第五个元素 (l, r) = (1, 5)\ ((P_l, P_r) = (1, 4) \in S). P 变为 (4, 5, 2, 3, 1, 6).
- 将第二个和第三个元素交换为 (l, r) = (2, 3)\ ((P_r, P_l) = (2, 5) \in S). P 变为 (4, 2, 5, 3, 1, 6).
- 将第一个和第五个元素交换为 (l, r) = (1, 5)\ ((P_r, P_l) = (1, 4) \in S). P 变为 (1, 2, 5, 3, 4, 6).
这是通过操作可获得的按字典顺序排列的最小排列。