Farmer John's Favorite Permutation

문제

Farmer John has a permutation $pp$ of length $NN$ ($2\le N\le {10}^5)2\; \backslash leq\; N\; \backslash leq\; 10^5)$, containing each positive integer from $11$ to $NN$ exactly once. However, Farmer Nhoj has broken into FJ's barn and disassembled $pp$. To not be too cruel, FN has written some hints that will help FJ reconstruct $pp$. While there is more than one element remaining in $pp$, FN does the following:

Let the remaining elements of $pp$ be $p_1^{\mathrm{\prime }},p_2^{\mathrm{\prime }},\dots ,p_n^{\mathrm{\prime }}p\text{'}\_1,\; p\text{'}\_2,\; \backslash dots\; ,\; p\text{'}\_n$,

• If $p_1^{\mathrm{\prime }}>p_n^{\mathrm{\prime }}p\text{'}\_1\; >\; p\text{'}\_n$, he writes down $p_2^{\mathrm{\prime }}p\text{'}\_2$ and removes $p_1^{\mathrm{\prime }}p\text{'}\_1$ from the permutation.
• Otherwise, he writes down $p_{n-1}^{\mathrm{\prime }}p\text{'}\_\{n-1\}$ and removes $p_n^{\mathrm{\prime }}p\text{'}\_n$ from the permutation.

At the end, Farmer Nhoj will have written down $N-1N\; -\; 1$ integers $h_1,h_2,\dots ,h_{N-1}h\_1,\; h\_2,\; \backslash dots,\; h\_\{N-1\}$, in that order. Given $hh$, Farmer John wants to enlist your help to reconstruct the lexicographically minimum $pp$ consistent with Farmer Nhoj's hints, or determine that Farmer Nhoj must have made a mistake. Recall that if you are given two permutations $pp$ and $p^{\mathrm{\prime }}p\text{'}$, $pp$ is lexicographically smaller than $p^{\mathrm{\prime }}p\text{'}$ if at the first position $ii$ where the two differ.

입력

Each input consists of $TT$ independent test cases ($1\le T\le 101\backslash le\; T\backslash le\; 10$). Each test case is described as follows:

The first line contains $NN$.

The second line contains $N-1N\; -\; 1$ integers $h_1,h_2,\dots ,h_{N-1}h\_1,\; h\_2,\; \backslash dots,\; h\_\{N-1\}$ ($1\le h_i\le N1\backslash le\; h\_i\backslash le\; N$).

출력

Output $TT$ lines, one for each test case.

If there is a permutation $pp$ of $1\dots N1\backslash dots\; N$ consistent with $hh$, output the lexicographically smallest such $pp$. If no such $pp$ exists, output $-1-1$.

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

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