← 返回题目列表

Codeforces · 1656/G

G. 循环回文

中文机器翻译题面 查看原题

如果对于所有 $$$1 \leq i \leq n$$$,$$$a_i = a_{n-i+1}$$$,我们说 $$$n$$$ 整数序列 $$$a_1, a_2, \ldots, a_n$$$ 是回文。给定一个 $$$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\}$$$ 的双射函数。如果 $$$1, \sigma(1), \sigma^2(1), \ldots, \sigma^{n-1}(1)$$$ 是两两不同的数,则我们说排列 $$$\sigma$$$ 是循环排列。这里 $$$\sigma^m(1)$$$ 表示 $$$\underbrace{\sigma(\sigma(\ldots \sigma}_{m \text{ times}}(1) \ldots))$$$。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,如果存在循环排列,则输出一行“是”,否则输出一行“否”。

如果答案为“是”,则输出额外一行,其中包含 $$$n$$$ 整数 $$$\sigma(1)、\sigma(2)、\ldots、\sigma(n)$$$ 排列。如果有多个排列,您可以打印任何一个。

示例

输入 #1

3
4
1 2 2 1
3
1 2 1
7
1 3 3 3 1 2 2

输出 #1

YES
3 1 4 2 
NO
YES
5 3 7 2 6 4 1