← 返回题目列表

AtCoder · arc216_e

E. 交换或反转

中文机器翻译题面 查看原题

分数: 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).

这是通过操作可获得的按字典顺序排列的最小排列。