题目背景

在“星港远征计划”中，停泊港口里排着一列编号互不相同的运输艇。
指挥系统给出了一组“兼容艇对” $S$：当某两个端点位置上的运输艇编号恰好属于这组兼容关系时，就允许执行特殊调度。
调度员可以直接交换这两个端点上的运输艇，也可以把这两个端点之间的整段编队整体翻转。

为了让离港顺序尽量整齐，你需要在所有可达的编队中，找出字典序最小的那一种排列。

题目描述

给定一个排列

$$P=(P_1,P_2,\ldots,P_N)$$

它是 $(1,2,\ldots,N)$ 的一个排列。

同时给定一个整数对集合

$$S=\{(x_1,y_1),(x_2,y_2),\ldots,(x_M,y_M)\}$$

你可以按任意顺序执行任意多次以下两种操作：

操作 1：交换

选择一对下标 $(l,r)$，满足 $1 \le l < r \le N$，并且

• $(P_l,P_r)\in S$，或者
• $(P_r,P_l)\in S$

此时你可以交换 $P$ 的第 $l$ 个元素与第 $r$ 个元素。

也就是把 $P$ 变为：

$$(P_1,\ldots,P_{l-1},P_r,P_{l+1},\ldots,P_{r-1},P_l,P_{r+1},\ldots,P_N)$$

操作 2：翻转区间

选择一对下标 $(l,r)$，满足 $1 \le l < r \le N$，并且

• $(P_l,P_r)\in S$，或者
• $(P_r,P_l)\in S$

此时你可以将区间 $[l,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
case1
case2
...
caseT

每组测试数据的格式为：

N M
P1 P2 ... PN
x1 y1
x2 y2
...
xM yM

---

输出格式

输出 $T$ 行。

第 $i$ 行输出第 $i$ 组测试数据的一组答案排列，格式为：

Q1 Q2 ... QN

其中 $(Q_1,Q_2,\ldots,Q_N)$ 是能够通过操作得到的字典序最小排列。

---

样例 #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 2 5 3 4 6
1 2 3 7 5 6 8 4

说明

对于第一组测试数据，可以按如下方式操作：

初始时：

$$P=(1,3,2,5,4,6)$$

1. 取 $(l,r)=(1,5)$。此时 $(P_l,P_r)=(1,4)\in S$，因此可以翻转区间 $[1,5]$。得到：

$$P=(4,5,2,3,1,6)$$

2. 取 $(l,r)=(2,3)$。此时 $(P_r,P_l)=(2,5)\in S$，因此可以交换第 $2$ 与第 $3$ 个元素。得到：

$$P=(4,2,5,3,1,6)$$

3. 再取 $(l,r)=(1,5)$。此时 $(P_r,P_l)=(1,4)\in S$，因此可以交换第 $1$ 与第 $5$ 个元素。得到：

$$P=(1,2,5,3,4,6)$$

这就是所有可达排列中字典序最小的一个。

---

数据范围

• $1 \le T \le 3\times10^4$
• $2 \le N \le 2\times10^5$
• $1 \le M \le 2\times10^5$
• $P$ 是 $(1,2,\ldots,N)$ 的一个排列
• $1 \le x_i < y_i \le N$
• 若 $i \ne j$，则 $(x_i,y_i)\ne(x_j,y_j)$
• 所有测试数据中，$N$ 的总和不超过 $2\times10^5$
• 所有测试数据中，$M$ 的总和不超过 $2\times10^5$
• 输入中的所有值均为整数