[Solution] Mystic Permutation Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Mystic Permutation Codeforces Solution | Codeforces Problem Solution 2022

B. Mystic Permutation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Monocarp is a little boy who lives in Byteland and he loves programming.

Recently, he found a permutation of length n$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 p1,p2,…,pn$p_1,p_2,\dots ,p_n$ and the new one is q1,q2,…,qn$q_1,q_2,\dots ,q_n$ it must hold that

Monocarp is afraid of lexicographically large permutations. Can you please help him to find the lexicographically minimal mystic permutation?

Input

There are several test cases in the input data. The first line contains a single integer 

$$

Solution Click Below:-  CLICK HERE

t$t$ (1≤t≤200$1\le t\le 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$n$ (1≤n≤1000$1\le n\le 1000$) — the length of the permutation.

The second line of each test case contains n$n$ distinct positive integers p1,p2,…,pn$p_1,p_2,\dots ,p_n$ (1≤pi≤n$1\le p_i\le n$). It's guaranteed that p$p$ is a permutation, i. e. pi≠pj$p_i\ne p_j$ for all i≠j$i\ne j$.

Mystic Permutation Codeforces Solution 

Lex String Codeforces Solution

Infected Tree Codeforces Solution

Lena and Matrix Codeforces Solution

ANDfinity Codeforces Solution

It is guaranteed that the sum of n$n$ does not exceed 1000$1000$ over all test cases.

Output

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