/ 
Time Limit: 5 sec / Memory Limit: 1024 MiB
配点 : 1000 点
問題文
(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 個のテストケースが与えられるので，それぞれについて答えを求めてください．
制約
- 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 以下
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる．
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 に対する答えを出力せよ．
入力例 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
1 2 5 3 4 6 1 2 3 7 5 6 8 4
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) となる．
これが操作によって得られる辞書順最小の順列です．
Score : 1000 points
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.
Sample Input 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
Sample Output 1
1 2 5 3 4 6 1 2 3 7 5 6 8 4
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.