A14891 | Cycle Palindrome

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))$ .

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$ .

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.