AT_arc216_e.[ARC216E] Swap or Reverse

$ (1,2,\ldots,N) $ の順列 $ P=(P_1,P_2,\ldots,P_N) $ および整数の組の集合 $ S=\lbrace (x_1, y_1), (x_2,y_2),\ldots,(x_M,y_M)\rbrace $ が与えられます．

あなたは以下の $ 2 $ 種類の操作を好きな順番で何度でも行うことができます．

• $ (P_l,P_r)\in S $ または $ (P_r,P_l)\in S $ であるような $ (l,r)\ (1\leq l\lt r\leq N) $ を選び， $ 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) $ で置き換える．
• $ (P_l,P_r)\in S $ または $ (P_r,P_l)\in S $ であるような $ (l,r)\ (1\leq l\lt r\leq N) $ を選び， $ P $ の $ 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 $ $ \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 $ に対する答えを出力せよ．

Sample Explanation 1

$ 1 $ つ目のテストケースについて，以下のように操作をすることで $ 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) $ として $ 1 $ 番目から $ 5 $ 番目までの要素を反転する． $ P=(4,5,2,3,1,6) $ となる．
• $ (l,r)=(2,3)\ ((P_r,P_l)=(2,5)\in S) $ として $ 2 $ 番目の要素と $ 3 $ 番目の要素を入れ替える． $ P=(4,2,5,3,1,6) $ となる．
• $ (l,r)=(1,5)\ ((P_r,P_l)=(1,4)\in S) $ として $ 1 $ 番目の要素と $ 5 $ 番目の要素を入れ替える． $ P=(1,2,5,3,4,6) $ となる．

これが操作によって得られる辞書順最小の順列です．

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 $ は $ (1,2,\ldots,N) $ の順列
• $ 1\leq x_i\lt y_i\leq N $
• $ i\neq j $ ならば $ (x_i,y_i)\neq (x_j,y_j) $
• 全てのテストケースに対する $ N $ の総和は $ 2\times 10^5 $ 以下
• 全てのテストケースに対する $ M $ の総和は $ 2\times 10^5 $ 以下
• 入力は全て整数