AT_arc216_e [ARC216E] Swap or Reverse

给定一个 $(1, 2, \ldots, N)$ 的排列 $P = (P_1, P_2, \ldots, P_N)$ 以及一个二元组集合 $S = \{(x_1, y_1), (x_2, y_2), \ldots, (x_M, y_M)\}$。 你可以按任意顺序执行以下两种操作任意多次： - 选择一对 $(l, r)$（$1 \leq l < r \leq N$），使得 $(P_l, P_r) \in S$ 或 $(P_r, P_l) \in S$，然后交换 $P_l$ 和 $P_r$。 - 选择一对 $(l, r)$（$1 \leq l < r \leq N$），使得 $(P_l, P_r) \in S$ 或 $(P_r, P_l) \in S$，然后反转 $P_l\sim P_r$，形式化地，将 $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$ 组测试数据。

第一行一个正整数 $T$，表示有 $T$ 组数据。 对于每组数据，第一行两个正整数 $N,M$，第二行 $N$ 个正整数表示排列 $P$。接下来 $M$ 行，每行两个正整数 $x_i,y_i$ 表示集合 $S$ 中的元素。

$T$ 行，对于每组数据，输出一行一个长为 $N$ 的排列代表通过操作能得到的最小字典序的排列。

### 数据范围 - $1\le T \le 3\times 10^4$ - $2\le N \le 2\times 10^5$ - $1\le M \le 2\times 10^5$ - $1\le x_i