Permutation recovery
Contest: Codeforces Round 559 (Div. 1)
Difficulty rating: 2100
Tags: constructive algorithms, data structures, dfs and similar, graphs, greedy, math, sortings

Vasya has written some permutation $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$, so for all $$$1 \leq i \leq n$$$ it is true that $$$1 \leq p_i \leq n$$$ and all $$$p_1, p_2, \ldots, p_n$$$ are different. After that he wrote $$$n$$$ numbers $$$next_1, next_2, \ldots, next_n$$$. The number $$$next_i$$$ is equal to the minimal index $$$i < j \leq n$$$, such that $$$p_j > p_i$$$. If there is no such $$$j$$$ let's let's define as $$$next_i = n + 1$$$.

In the evening Vasya went home from school and due to rain, his notebook got wet. Now it is impossible to read some written numbers. Permutation and some values $$$next_i$$$ are completely lost! If for some $$$i$$$ the value $$$next_i$$$ is lost, let's say that $$$next_i = -1$$$.

You are given numbers $$$next_1, next_2, \ldots, next_n$$$ (maybe some of them are equal to $$$-1$$$). Help Vasya to find such permutation $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$, that he can write it to the notebook and all numbers $$$next_i$$$, which are not equal to $$$-1$$$, will be correct.

Input format:
The first line contains one integer $$$t$$$ — the number of test cases ($$$1 \leq t \leq 100\,000$$$).

Next $$$2 \cdot t$$$ lines contains the description of test cases,two lines for each. The first line contains one integer $$$n$$$ — the length of the permutation, written by Vasya ($$$1 \leq n \leq 500\,000$$$). The second line contains $$$n$$$ integers $$$next_1, next_2, \ldots, next_n$$$, separated by spaces ($$$next_i = -1$$$ or $$$i < next_i \leq n + 1$$$).

It is guaranteed, that the sum of $$$n$$$ in all test cases doesn't exceed $$$500\,000$$$.

In hacks you can only use one test case, so $$$T = 1$$$.

Output format:
Print $$$T$$$ lines, in $$$i$$$-th of them answer to the $$$i$$$-th test case.

If there is no such permutations $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$, that Vasya could write, print the only number $$$-1$$$.

In the other case print $$$n$$$ different integers $$$p_1, p_2, \ldots, p_n$$$, separated by spaces ($$$1 \leq p_i \leq n$$$). All defined values of $$$next_i$$$ which are not equal to $$$-1$$$ should be computed correctly $$$p_1, p_2, \ldots, p_n$$$ using defenition given in the statement of the problem. If there exists more than one solution you can find any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case for permutation $$$p = [1, 2, 3]$$$ Vasya should write $$$next = [2, 3, 4]$$$, because each number in permutation is less than next. It's easy to see, that it is the only satisfying permutation.

In the third test case, any permutation can be the answer because all numbers $$$next_i$$$ are lost.

In the fourth test case, there is no satisfying permutation, so the answer is $$$-1$$$.

Example input:
6
3
2 3 4
2
3 3
3
-1 -1 -1
3
3 4 -1
1
2
4
4 -1 4 5

Example output:
1 2 3
2 1
2 1 3
-1
1
3 2 1 4

Editorial:
Note that if there are indices $$$i < j$$$ for which the values $$$next_i$$$ and $$$next_j$$$ are defined and $$$i < j < next_i < next_j$$$ are satisfied, then there is no answer. Suppose that this is not true and there exists permutation $$$p_1, p_2, \ldots, p_n$$$. Note that since $$$j < next_i$$$ we get that $$$p_i > p_j$$$ (otherwise $$$next_i$$$ would not be the minimum position in which the number is greater than $$$p_i$$$). But then $$$p_j < p_i < p_{next_i}$$$, so $$$next_j$$$ is not the minimum position for $$$j$$$. Contradiction.
Now we prove that if for any pair of indices $$$i < j$$$ such condition is not satisfied, then the permutation always exists.
First, let's get rid of $$$next_i = -1$$$. If $$$next_i = -1$$$ let's say $$$next_i = i + 1$$$. Note that for any pair $$$i < j$$$ the condition $$$i < j < next_i < next_j$$$ is still not satisfied (since $$$next_i = i + 1$$$ cannot take part in such inequality).
Consider the following rooted tree with $$$n + 1$$$ vertices: the vertex with index $$$n + 1$$$ will be the root, and the ancestor of the vertex with index $$$i$$$ will be $$$next_i$$$. Since it is always $$$i < next_i$$$ we get the rooted tree.
Let's run the depth first search algorithm ($$$dfs$$$) from the vertex $$$n + 1$$$ in this tree. In this case, we will bypass the sons of each vertex in order from the smaller number to the larger one. Let's make some global variable $$$timer = n + 1$$$. Each time we come to the vertex $$$i$$$, we will make $$$p_i = timer$$$ and reduce $$$timer$$$ by $$$1$$$. Note that $$$p_1, p_2, \ldots, p_n$$$ will form a permutation of numbers from $$$1$$$ to $$$n$$$.
We prove that this permutation is the answer.
First of all, for all $$$i$$$ due to $$$next_i$$$ was the ancestor of $$$i$$$, we'll go there early and so $$$p_{next_i} > p_i$$$. Let $$$i < j < next_i$$$. We need to prove that we will come to the vertex $$$j$$$ later than to the vertex $$$i$$$. Note that then the vertex $$$next_i$$$ will be a descendant of $$$j$$$ in the tree, because if you start go from $$$j$$$ by $$$next$$$, you cannot jump over $$$next_i$$$, because otherwise there is an index $$$x$$$, for which the inequality $$$i < x < next_i < next_x$$$ is satisfied. But such pair of indexes $$$i$$$, $$$x$$$ cannot exist. We'll get to $$$j$$$ later because the son of $$$next_i$$$, which is the ancestor of $$$j$$$ will be $$$\geq j$$$, and thus $$$> i$$$.
That is, we understood what is the criterion of the answer and learned how to quickly build an answer, if this criterion is satisfied. But we still need to check that this criterion is satisfied. This can be done by some simple linear algorithm. But we will do this: let's make an algorithm for constructing the answer (without checking the criterion) and find the permutation $$$p$$$. Now, using the stack and the standard algorithm, we find the $$$next_i$$$ values for it. If they match the given $$$next_i$$$, then we have found the answer, otherwise, let's say that there is no answer. If the criterion is satisfied we will find the answer and if not satisfied after checking $$$p$$$ we will say there are no answers.
Complexity: $$$O(n)$$$ time and memory.