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

我们称一个由 $n$ 个整数组成的序列 $a_1, a_2, \ldots, a_n$ 是回文序列，当且仅当对所有 $1 \leq i \leq n$，均有 $a_i = a_{n-i+1}$。现给定一个由 $n$ 个整数组成的序列 $a_1, a_2, \ldots, a_n$，你需要判断是否存在一个循环置换 $\sigma$，使得重排后的序列 $a_{\sigma(1)}, a_{\sigma(2)}, \ldots, a_{\sigma(n)}$ 构成回文序列。

集合 $\{1, 2, \ldots, n\}$ 的一个置换是指从 $\{1, 2, \ldots, n\}$ 到 $\{1, 2, \ldots, n\}$ 的一个双射函数。我们称一个置换 $\sigma$ 是循环置换，当且仅当 $1, \sigma(1), \sigma^2(1), \ldots, \sigma^{n-1}(1)$ 两两互不相同。此处 $\sigma^m(1)$ 表示将 $\sigma$ 连续作用 $m$ 次于 $1$ 所得的结果，即 $\underbrace{\sigma(\sigma(\ldots \sigma}_{m \text{ 次}}(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$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 3 \cdot 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$），表示序列的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, \ldots, a_n$（$1 \leq a_i \leq n$）。

所有测试用例的 $n$ 值之和不超过 $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.

对于每个测试用例，如果存在一个循环排列，则输出一行 YES；否则输出一行 NO。

如果答案为 YES，则再输出一行包含 $n$ 个整数 $\sigma(1), \sigma(2), \ldots, \sigma(n)$ 的排列。若存在多个满足条件的排列，输出任意一个即可。