409888: GYM103828 A 2 Arrays Problem

You are given $$$2$$$ arrays $$$A$$$ and $$$G$$$ both of the same length $$$N$$$. You are asked to create a permutation $$$P$$$ of length $$$N$$$ such that for any pair of integers $$$i,j$$$ $$$(1 \le i,j \le n)$$$ where $$$i\neq j$$$ if $$$G_i = G_j$$$ and $$$A_i \ge A_j$$$ then it should satisfy that $$$P_i > P_j$$$.

Since there may be a lot of permutations that satisfy the above requirements, you are asked to print the lexicographically smallest permutation.

If there is no such permutation that satisfies the above requirements, print $$$ - 1 $$$.

The first line of input contains a single integer $$$T$$$, the number of test cases.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$, the number of elements in each array.

The second line of each test case contains $$$n$$$ integers $$$A_1,A_2,\dots,A_n$$$ $$$(1 \le A_i \le 10^9)$$$, the elements of array $$$A$$$.

The third line of each test case contains $$$n$$$ integers $$$G_1,G_2,\dots,G_n$$$ $$$(1 \le G_i \le 10^5)$$$, the elements of array $$$G$$$.

The sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Print $$$T$$$ lines, each containing the lexicographically smallest permutation, or $$$-1$$$ if no such permutation exists.

2
8
1 8 1 7 4 6 6 5
1 2 2 2 1 2 1 1
8
1 8 1 4 4 7 6 5
1 8 2 2 1 7 4 1

1 5 2 4 6 3 8 7 
1 2 3 4 5 6 7 8 

For the second test case, we can check that the permutation satisfies the requirements.

• $$$A_1 < A_5$$$ and $$$G_1 = G_5$$$ $$$\implies$$$ $$$P_1 < P_5$$$ .
• $$$A_1 < A_8$$$ and $$$G_1 = G_8$$$ $$$\implies$$$ $$$P_1 < P_8$$$ .
• $$$A_5 < A_8$$$ and $$$G_5 = G_8$$$ $$$\implies$$$ $$$P_5 < P_8$$$ .
• $$$A_3 < A_4$$$ and $$$G_3 = G_4$$$ $$$\implies$$$ $$$P_3 < P_4$$$ .

Also, it's the lexicographically smallest permutation.

A permutation of length $$$N$$$ is a sequence of integers from $$$1$$$ to $$$N$$$ of length $$$N$$$ containing each number exactly once. For example, $$$[1], [4,3,5,1,2], [3,2,1]$$$ are permutations, and $$$[1,1], [0,1], [2,2,1,4]$$$ are not.

Sequence $$$X_1, X_2, \dots , X_N$$$ is lexicographically smaller than sequence $$$Y_1, Y_2, \dots , Y_N$$$ if there exists an integer $$$r$$$ $$$(0 \le r < N)$$$ such that $$$X_1 = Y_1, X_2 = Y_2, \dots , X_r = Y_r$$$ and $$$X_{r+1} < Y_{r+1}$$$.