CF1685D2 Permutation Weight (Hard Version)

**这是本题的困难版本。** **简单版本和困难版本的区别在于对你所构造的排列的限制。** **在本题中你需要输出所有权值最小化的排列中字典序最小的那个。** 给定一个 $1\sim n$ 的排列 $p$。 对于一个 $1\sim n$ 的排列 $q$，定义其权值为： $$|q_1-p_{q_2}|+|q_2-p_{q_3}|+|q_3-p_{q_4}|+\cdots+|q_{n-1}-p_{q_n}|+|q_n-p_{q_1}|$$ 找出所有满足权值最小化的 $1\sim n$ 的排列 $q$ 中 **字典序最小** 的那个。 我们称两个 $1\sim n$ 的排列 $a,b$ 有 $a$ 比 $b$ 字典序小仅当存在整数 $i(1\leq i\leq n)$ 满足 $a_i

第一行输入一个整数 $t(1\leq t\leq100)$ 表示数据组数，接下来对于每组数据： 第一行输入一个整数 $n(2\leq n\leq200;\sum n\leq400)$ 表示排列长度。 接下来一行输入 $n$ 个整数表示排列 $p(1\leq p_i\leq n)$。

对于每组数据： 输出 $n$ 个整数表示你求出的权值最小化且字典序最小的排列 $q$。

In the first test case, there are two permutations of length $ 2 $ : $ (1, 2) $ and $ (2, 1) $ . Permutation $ (1, 2) $ has weight $ |1 - p_2| + |2 - p_1| = 0 $ , and the permutation $ (2, 1) $ has the same weight: $ |2 - p_1| + |1 - p_2| = 0 $ . In this version, you have to output the lexicographically smaller of them — $ (1, 2) $ . In the second test case, the weight of the permutation $ (1, 3, 4, 2) $ is $ |1 - p_3| + |3 - p_4| + |4 - p_2| + |2 - p_1| = |1 - 1| + |3 - 4| + |4 - 3| + |2 - 2| = 2 $ . There are no permutations with smaller weights. In the third test case, the weight of the permutation $ (1, 3, 4, 2, 5) $ is $ |1 - p_3| + |3 - p_4| + |4 - p_2| + |2 - p_5| + |5 - p_1| = |1 - 3| + |3 - 2| + |4 - 4| + |2 - 1| + |5 - 5| = 4 $ . There are no permutations with smaller weights.