AT_arc216_e [ARC216E] Swap or Reverse

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.

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 $ T $ lines. The $ i $ -th line should contain the answer to $ \mathrm{case}_i $ .

### Sample Explanation 1 For the first test case, you can obtain $ P = (1, 2, 5, 3, 4, 6) $ by performing the operations as follows. - Initially, $ P = (1, 3, 2, 5, 4, 6) $ . - Reverse the elements from the first to the fifth with $ (l, r) = (1, 5)\ ((P_l, P_r) = (1, 4) \in S) $ . $ P $ becomes $ (4, 5, 2, 3, 1, 6) $ . - Swap the second and third elements with $ (l, r) = (2, 3)\ ((P_r, P_l) = (2, 5) \in S) $ . $ P $ becomes $ (4, 2, 5, 3, 1, 6) $ . - Swap the first and fifth elements with $ (l, r) = (1, 5)\ ((P_r, P_l) = (1, 4) \in S) $ . $ P $ becomes $ (1, 2, 5, 3, 4, 6) $ . This is the lexicographically smallest permutation obtainable by the operations. ### 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.