← 返回题目列表

Codeforces · 1689/B

B. 神秘排列

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

Monocarp 是一个住在 Byteland 的小男孩,他喜欢编程。

最近,他发现了一个长度为$$$n$$$的排列。他必须想出一个神秘的排列。它必须是一种新的排列,并且每个位置都与旧的排列不同。

更正式地说,如果旧排列是 $$$p_1,p_2,\ldots,p_n$$$ 而新排列是 $$$q_1,q_2,\ldots,q_n$$$ 则必须满足 $$$$$$p_1\neq q_1, p_2\neq q_2, \ldots ,p_n\neq q_n.$$$$$$

Monocarp 害怕字典顺序上的大排列。你能帮他找到字典顺序上最小的神秘排列吗?

输入

输入数据中有多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 200$$$) — 测试用例的数量。接下来是测试用例描述。

每个测试用例的第一行包含一个正整数 $$$n$$$ ($$$1\leq n\leq 1000$$$) — 排列的长度。

每个测试用例的第二行包含 $$$n$$$ 不同的正整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$)。保证 $$$p$$$ 是一个排列,i。 e. $$$p_i \neq p_j$$$ 对于所有 $$$i \neq j$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。

输出

对于每个测试用例,输出 $$$n$$$ 正整数 - 按字典顺序排列的最小神秘排列。如果这样的排列不存在,则输出$$$-1$$$。

示例

输入 #1

4
3
1 2 3
5
2 3 4 5 1
4
2 3 1 4
1
1

输出 #1

2 3 1
1 2 3 4 5
1 2 4 3
-1

注意

在第一个测试用例中,可能的神秘排列是 $$$[2,3,1]$$$ 和 $$$[3,1,2]$$$。按字典顺序,两者中较小的是 $$$[2,3,1]$$$。

在第二个测试用例中,$$$[1,2,3,4,5]$$$ 是字典顺序上最小的排列,而且它也是神秘的。

在第三个测试用例中,可能的神秘排列是 $$$[1,2,4,3]$$$, $$$[1,4,2,3]$$$, $$$[1,4,3,2]$$$, $$$[3,1,4,2]$$$, $$$[3,2,4,1]$$$, $$$[3,4,2,1]$$$、$$$[4,1,2,3]$$$、$$$[4,1,3,2]$$$ 和 $$$[4,3,2,1]$$$。最小的是$$$[1,2,4,3]$$$。