Permutation Weight (Hard Version)
Contest: Codeforces Round 794 (Div. 1)
Difficulty rating: 3500
Tags: constructive algorithms, greedy

This is a hard version of the problem. The difference between the easy and hard versions is that in this version, you have to output the lexicographically smallest permutation with the smallest weight.

You are given a permutation $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$.

Let's define the weight of the permutation $$$q_1, q_2, \ldots, q_n$$$ of integers from $$$1$$$ to $$$n$$$ as $$$$$$|q_1 - p_{q_{2}}| + |q_2 - p_{q_{3}}| + \ldots + |q_{n-1} - p_{q_{n}}| + |q_n - p_{q_{1}}|$$$$$$

You want your permutation to be as lightweight as possible. Among the permutations $$$q$$$ with the smallest possible weight, find the lexicographically smallest.

Permutation $$$a_1, a_2, \ldots, a_n$$$ is lexicographically smaller than permutation $$$b_1, b_2, \ldots, b_n$$$, if there exists some $$$1 \le i \le n$$$ such that $$$a_j = b_j$$$ for all $$$1 \le j < i$$$ and $$$a_i<b_i$$$.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 200$$$)  — the size of the permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are distinct)  — the elements of the permutation.

The sum of $$$n$$$ over all test cases doesn't exceed $$$400$$$.

Output format:
For each test case, output $$$n$$$ integers $$$q_1, q_2, \ldots, q_n$$$ ($$$1 \le q_i \le n$$$, all $$$q_i$$$ are distinct)  — the lexicographically smallest permutation with the smallest weight.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
2
2 1
4
2 3 1 4
5
5 4 3 2 1

Example output:
1 2 
1 3 4 2 
1 3 4 2 5

Editorial:
We will start by proving that the weight is at least $$$2(k-1)$$$ (where $$$k$$$ is the number of cycles), and understanding the structure of optimal permutations in the process.
Again, consider splitting of $$$p$$$ into cycles (where a cycle is an array $$$[a_1, a_2, \ldots, a_m]$$$ such that $$$p_{a_i} = a_{i \bmod m +1}$$$ for $$$1 \le i \le m$$$). Let's say there are $$$k$$$ of such cycles.
Now, consider a graph $$$G$$$ on $$$n$$$ nodes, and draw an edge from $$$q_i$$$ to $$$p_{q_{i+1}}$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$ (there may be self-loops and multi-edges here). Each node has one incoming and outgoing edge, so the entire graph is split into several cycles. Consider any such cycle $$$(b_1, b_2, \ldots, b_m)$$$, where all $$$b_i$$$ are distinct. Its contribution to the answer is $$$|b_1 - b_2| + |b_2 - b_3| + \ldots + |b_m - b_1|$$$. We will show that:
• This value is at least $$$2(m-1)$$$.Proof: Wlog $$$b_i$$$ is the smallest among $$$b$$$ and $$$b_j$$$ is the largest, with $$$i<j$$$. Then $$$|b_1 - b_2| + |b_2 - b_3| + \ldots + |b_m - b_1| = (|b_i - b_{i+1}| + \ldots + |b_{j-1} - b_j|) + (|b_j - b_{j+1}| + \ldots + |b_{i-1} - b_i|) \ge $$$ $$$\le 2|b_i - b_j| \ge 2(m-1)$$$.
• It's $$$2(m-1)$$$ only when the numbers on the cycle are some $$$m$$$ consecutive numbers and are increasing on the path from the smallest number to the largest and decreasing on the way back.Proof: It's just the case when all the inequalities in the expression above become equalities.
Now, assign each cycle of $$$p$$$ a number from $$$1$$$ to $$$k$$$ and consider the graph $$$G_1$$$ on $$$k$$$ nodes, draw an edge between the nodes corresponding to the cycles where $$$q_i$$$ and $$$p_{q_{i+1}}$$$ belong. As $$$q_i$$$ and $$$p_{q_i}$$$ are in the same cycle for each $$$i$$$, we get that every two consecutive edges we draw share a node. As we will draw an edge from every cycle, the graph is connected.
Each edge in $$$G_1$$$ corresponds to an edge in $$$G$$$ (edge between $$$q_i$$$ and $$$p_{q_{i+1}}$$$ in $$$G$$$ corresponds to an edge in $$$G_1$$$ between the nodes corresponding to the cycles where $$$q_i$$$ and $$$p_{q_{i+1}}$$$ belong).
Now, consider any spanning tree in graph $$$G_1$$$. Clearly, any cycle of length $$$m$$$ in $$$G_1$$$ can contain at most $$$m-1$$$ edges from it (if it contained $$$m$$$ edges from it, we would have a cycle in $$$G_1$$$). So, the total sum of $$$(m-1)$$$ over all cycles in $$$G$$$ is at least $$$k-1$$$, and therefore the total contribution to the weight is at least $$$2(k-1)$$$.
Now let's give a characterization of all permutations $$$q$$$ which have the weight $$$2(k-1)$$$. It turns out, that they are in correspondence with graphs $$$G$$$ on $$$n$$$ nodes which satisfy the following conditions:
• Each node has one incoming and one outgoing edge (and therefore graph is split into cycles).
• In $$$G$$$, if a cycle has length $$$m$$$, then it consists of $$$m$$$ consecutive integers, where numbers go up from the smallest number to the largest and down on the way back
• The sum of $$$m-1$$$ over all cycles is precisely $$$k-1$$$.
• If we draw an edge between two cycles of $$$p$$$ if an element of the first cycle is connected to the element of the second cycle in $$$G$$$, this graph on $$$k$$$ nodes is connected.
Each such graph is a corresponding graph of some optimal permutation $$$q$$$. The proof is left for the reader as an exercise.
Now, how to solve our problem? Let's build $$$q$$$ element by element. The weights of all cyclic shifts of the same permutation are the same, so we start with $$$q_1 = 1$$$. Now, the only subproblem we have to be able to solve is to check if the current prefix $$$q$$$ of length $$$l$$$ is a prefix of some permutation with weight $$$2(k-1)$$$. So, we have to check if our current $$$l-1$$$ edges $$$q_i \to p_{q_{i+1}}$$$ can be a subset of some graph $$$G$$$ satisfying all the conditions above.
Denote these edges $$$(u_1, v_1), \ldots, (u_{l-1}, v_{l-1})$$$. If edge has $$$u_i<v_i$$$, consider segment $$$[l_i, r_i] = [u_i, v_i]$$$, and call it right segment. If edge has $$$u_i>v_i$$$, consider segment $$$[l_i, r_i] = [v_i, u_i]$$$, and call it left segment. If $$$u_i = v_i$$$, call $$$u_i$$$ loop node.
We can show that the following criteria are sufficient:
• No two right segments intersect internally.
• No two left segments intersect internally.
• No right/left segment contains a loop node.
• Consider a graph on $$$k$$$ nodes, corresponding to the cycles of $$$p$$$. For each $$$1 \le i \le n-1$$$, if $$$[i, i+1]$$$ is contained in some segment, draw an edge between the corresponding cycles in which $$$i$$$, $$$i+1$$$ are. Then, this graph can't have a cycle (has to be a forest).
• Consider a graph on $$$k$$$ nodes, corresponding to the cycles of $$$p$$$. For each $$$1 \le i \le n-1$$$, unless $$$i$$$ or $$$i+1$$$ are loop nodes, or $$$i$$$ is the right end of two segments, or $$$i+1$$$ is the left end of two segments, draw an edge between the corresponding cycles in which $$$i$$$, $$$i+1$$$ are. Then, this graph must be connected.
These conditions may sound complicated but they are very simple implications of the conditions on $$$G$$$ above. The proof that if these conditions are satisfied then edges form a subset of some valid $$$G$$$ is left to the reader as an exercise too (tutorial is already too long, sorry).
Total complexity is $$$O(n^3)$$$, as we can do up $$$O(n^2)$$$ checks, and each check takes $$$O(n)$$$ time.