Problem Statement

You are given a permutation $P = (P_1, P_2, \ldots, P_N)$ of $(1, 2, \ldots, N)$ and a set of pairs of integers $S = \lbrace (x_1, y_1), (x_2, y_2), \ldots, (x_M, y_M) \rbrace$.

You can perform the following two types of operations any number of times in any order.

• Choose $(l, r)\ (1 \leq l < r \leq N)$ such that $(P_l, P_r) \in S$ or $(P_r, P_l) \in S$, and swap the $l$-th and $r$-th elements of $P$. That is, replace $P$ with $(P_1, \ldots, P_{l-1}, P_r, P_{l+1}, \ldots, P_{r-1}, P_l, P_{r+1}, \ldots, P_N)$.
• Choose $(l, r)\ (1 \leq l < r \leq N)$ such that $(P_l, P_r) \in S$ or $(P_r, P_l) \in S$, and reverse the elements from the $l$-th to the $r$-th of $P$. That is, replace $P$ with $(P_1, \ldots, P_{l-1}, P_r, P_{r-1}, \ldots, P_{l+1}, P_l, P_{r+1}, \ldots, P_N)$.

Find the lexicographically smallest permutation obtainable by the operations.

You are given $T$ test cases; solve each of them.

Constraints

• $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$ is a permutation of $(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$.
• The sum of $N$ over all test cases is at most $2 \times 10^5$.
• The sum of $M$ over all test cases is at most $2 \times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N M
P_1 P_2 \ldots P_N
x_1 y_1
x_2 y_2
\vdots
x_M y_M

Output

Output $T$ lines. The $i$-th line should contain the answer to $\mathrm{case}_i$.