A16229 | Selling a Menagerie

You are the owner of a menagerie consisting of $n$ animals numbered from $1$ to $n$ . However, maintaining the menagerie is quite expensive, so you have decided to sell it!

It is known that each animal is afraid of exactly one other animal. More precisely, animal $i$ is afraid of animal $a_i$ ( $a_i \neq i$ ). Also, the cost of each animal is known, for animal $i$ it is equal to $c_i$ .

You will sell all your animals in some fixed order. Formally, you will need to choose some permutation $^\dagger$ $p_1, p_2, \ldots, p_n$ , and sell animal $p_1$ first, then animal $p_2$ , and so on, selling animal $p_n$ last.

When you sell animal $i$ , there are two possible outcomes:

- If animal $a_i$ was sold before animal $i$ , you receive $c_i$ money for selling animal $i$ .
- If animal $a_i$ was not sold before animal $i$ , you receive $2 \cdot c_i$ money for selling animal $i$ . (Surprisingly, animals that are currently afraid are more valuable).

Your task is to choose the order of selling the animals in order to maximize the total profit.

For example, if $a = [3, 4, 4, 1, 3]$ , $c = [3, 4, 5, 6, 7]$ , and the permutation you choose is $[4, 2, 5, 1, 3]$ , then:

- The first animal to be sold is animal $4$ . Animal $a_4 = 1$ was not sold before, so you receive $2 \cdot c_4 = 12$ money for selling it.
- The second animal to be sold is animal $2$ . Animal $a_2 = 4$ was sold before, so you receive $c_2 = 4$ money for selling it.
- The third animal to be sold is animal $5$ . Animal $a_5 = 3$ was not sold before, so you receive $2 \cdot c_5 = 14$ money for selling it.
- The fourth animal to be sold is animal $1$ . Animal $a_1 = 3$ was not sold before, so you receive $2 \cdot c_1 = 6$ money for selling it.
- The fifth animal to be sold is animal $3$ . Animal $a_3 = 4$ was sold before, so you receive $c_3 = 5$ money for selling it.

Your total profit, with this choice of permutation, is $12 + 4 + 14 + 6 + 5 = 41$ . Note that $41$ is not the maximum possible profit in this example.

$^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ( $2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ( $n=3$ , but $4$ is present in the array).

The first line of the input contains an integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases.

Then follow the descriptions of the test cases.

The first line of each test case description contains an integer $n$ ( $2 \le n \le 10^5$ ) — the number of animals.

The second line of the test case description contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le n$ , $a_i \neq i$ ) — $a_i$ means the index of the animal that animal $i$ is afraid of.

The third line of the test case description contains $n$ integers $c_1, c_2, \dots, c_n$ ( $1 \le c_i \le 10^9$ ) — the costs of the animals.

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

Output $t$ lines, each containing the answer to the corresponding test case. The answer should be $n$ integers — the permutation $p_1, p_2, \ldots, p_n$ , indicating in which order to sell the animals in order to maximize the profit. If there are multiple possible answers, you can output any of them.