Mystic Permutation

题意翻译

给定一个 $[1,n]$的排列，要求你构造一个新的 $[1,n]$ 的排列，使得这两个排列之间的任意一个相同位置的元素都不相同，且满足这个排列的字典序最小。 如果无法构造出这样的序列则输出$-1$

题目描述

Monocarp is a little boy who lives in Byteland and he loves programming. Recently, he found a permutation of length $ n $ . He has to come up with a mystic permutation. It has to be a new permutation such that it differs from the old one in each position. More formally, if the old permutation is $ p_1,p_2,\ldots,p_n $ and the new one is $ q_1,q_2,\ldots,q_n $ it must hold that $ $p_1\neq q_1, p_2\neq q_2, \ldots ,p_n\neq q_n. $ $ Monocarp is afraid of lexicographically large permutations. Can you please help him to find the lexicographically minimal mystic permutation?

输入输出格式

输入格式

There are several test cases in the input data. The first line contains a single integer $ t $ ( $ 1\leq t\leq 200 $ ) — the number of test cases. This is followed by the test cases description. The first line of each test case contains a positive integer $ n $ ( $ 1\leq n\leq 1000 $ ) — the length of the permutation. The second line of each test case contains $ n $ distinct positive integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \leq p_i \leq n $ ). It's guaranteed that $ p $ is a permutation, i. e. $ p_i \neq p_j $ for all $ i \neq j $ . It is guaranteed that the sum of $ n $ does not exceed $ 1000 $ over all test cases.

输出格式

For each test case, output $ n $ positive integers — the lexicographically minimal mystic permutations. If such a permutation does not exist, output $ -1 $ instead.

输入输出样例

输入样例 #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

说明

In the first test case possible permutations that are mystic are $ [2,3,1] $ and $ [3,1,2] $ . Lexicographically smaller of the two is $ [2,3,1] $ . In the second test case, $ [1,2,3,4,5] $ is the lexicographically minimal permutation and it is also mystic. In third test case possible mystic permutations are $ [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] $ and $ [4,3,2,1] $ . The smallest one is $ [1,2,4,3] $ .

**题意翻译**

给定一个 $[1,n]$ 的排列，要求构造一个新的 $[1,n]$ 的排列，使得这两个排列之间的任意一个相同位置的元素都不相同，并且这个排列的字典序最小。如果无法构造出这样的序列则输出 $-1$。

**题目描述**

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 \neq j$，有 $p_i \neq p_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]$。**题意翻译** 给定一个 $[1,n]$ 的排列，要求构造一个新的 $[1,n]$ 的排列，使得这两个排列之间的任意一个相同位置的元素都不相同，并且这个排列的字典序最小。如果无法构造出这样的序列则输出 $-1$。 **题目描述** 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 \neq j$，有 $p_i \neq p_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]$。