Cycle Palindrome
Contest: CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 3200
Tags: constructive algorithms, graphs, math

We say that a sequence of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ is a palindrome if for all $$$1 \leq i \leq n$$$, $$$a_i = a_{n-i+1}$$$. You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ and you have to find, if it exists, a cycle permutation $$$\sigma$$$ so that the sequence $$$a_{\sigma(1)}, a_{\sigma(2)}, \ldots, a_{\sigma(n)}$$$ is a palindrome.

A permutation of $$$1, 2, \ldots, n$$$ is a bijective function from $$$\{1, 2, \ldots, n\}$$$ to $$$\{1, 2, \ldots, n\}$$$. We say that a permutation $$$\sigma$$$ is a cycle permutation if $$$1, \sigma(1), \sigma^2(1), \ldots, \sigma^{n-1}(1)$$$ are pairwise different numbers. Here $$$\sigma^m(1)$$$ denotes $$$\underbrace{\sigma(\sigma(\ldots \sigma}_{m \text{ times}}(1) \ldots))$$$.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the size of the sequence.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

The sum of $$$n$$$ for all test cases is at most $$$2 \cdot 10^5$$$.

Output format:
For each test case, output one line with YES if a cycle permutation exists, otherwise output one line with NO.

If the answer is YES, output one additional line with $$$n$$$ integers $$$\sigma(1), \sigma(2), \ldots, \sigma(n)$$$, the permutation. If there is more than one permutation, you may print any.

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

Example input:
3
4
1 2 2 1
3
1 2 1
7
1 3 3 3 1 2 2

Example output:
YES
3 1 4 2 
NO
YES
5 3 7 2 6 4 1

Editorial:
We clearly see that the following two conditions are necessary:
• Each number must be repeated an even number of time except possibly one of the numbers. (This is necessary to find any permutation that results in a palindrome, not just a cycle).
• If $$$n$$$ is odd, it can not be that the number $$$a_{(n+1)/2}$$$ appears only one time. (Otherwise, the permutation would need to have one fixed point).
We will see that those two conditions are sufficient. First, let's focus on the $$$n$$$ even case. Find any permutation $$$\sigma$$$ so that applying it results in a palindrome. This permutation will have a cycle decomposition. We are going to merge all those cycles in one big cycle.
To do so, we will first merge the cycles so that indices $$$i$$$ and $$$n-i+1$$$ are in the same cycle for all $$$i$$$. Note that, since $$$a_{\sigma(i)} = a_{\sigma(n-i+1)}$$$ we can define a new permutation $$$\sigma'$$$ with $$$\sigma'(n-i+1) = \sigma(i)$$$ and $$$\sigma'(i) = \sigma(n-i+1)$$$ and the permutation $$$\sigma'$$$ will still generate a palindrome and $$$i$$$ and $$$n-i+1$$$ will be in the same cycle. We iterate over all the $$$i$$$s and merge all such cycles. Note that we need to keep track efficiently of which indices are in the same cycle, so we should use union-find data structure.
Now we have $$$m$$$ disjoint cycles which are symmetric, that is $$$i$$$ and $$$n-i+1$$$ are in the same cycle. If $$$m = 1$$$ we've won. Otherwise, let $$$i_1, \ldots, i_m$$$ be indices belonging to each of the cycles and let $$$\sigma$$$ be our current permutation. Note that if we define $$$\sigma'(i_j) = \sigma(n-i_{j+1}+1)$$$ and $$$\sigma'(n-i_j+1) = \sigma(i_{j+1})$$$ for $$$j = 1, \ldots, m-1$$$ and $$$\sigma'(i_m) = \sigma(i_1)$$$, $$$\sigma'(n-i_m+1) = \sigma(n-i_1+1)$$$, we have another permutation $$$\sigma'$$$ which results in a palindrome and consists of only one cycle, so we're done.
There are different ways of handling the case when $$$n$$$ is odd, the one that requires least casework for this solution is noticing that in the $$$n$$$ odd case we can still merge symmetric cycles with no issues, and that the only thing that could make the last step fail would be to choose some index $$$i_j$$$ so that $$$n-i_j+1 = i_j$$$. So we have to be careful not to choose $$$i_j = \frac{n+1}{2}$$$, and in particular this means that the cycle that contains the middle element can not be a fixed point. If the second condition is satisfied, this can be achieved easily in the initial permutation we choose.
Alternative solution:
Notice that the above solution has $$$O(n \alpha (n) )$$$ complexity because of union-find. Actually, a $$$O(n)$$$ complexity can be achieved, we describe briefly an alternative solution with that complexity. We focus on the case when $$$n$$$ is even. The idea is to start with a permutation whose cycles are already symmetric. In order to do so, we construct a graph whose vertices are the numbers that appear in the sequence and for each $$$1 \leq i \leq \frac{n}{2}$$$ we add an edge between $$$a_i$$$ and $$$a_{n-i+1}$$$. Now note that for each of the connected components of the graph we can obtain a symmetric cycle resulting in a palindrome from an Eulerian tour of the graph.